{"entities":{"Q789386":{"pageid":791234,"ns":120,"title":"Item:Q789386","lastrevid":64352436,"modified":"2026-04-11T19:17:07Z","type":"item","id":"Q789386","labels":{"en":{"language":"en","value":"On the structure of \\(\\Delta_ 2\\!^ p\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3845568"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789386$38D5B3AE-9F14-4A30-8280-9E50A5FA0AF7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"df1c73c73fc7c3356df4cccec00a50847d2799fd","datavalue":{"value":{"text":"On the structure of \\(\\Delta_ 2\\!^ p\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q789386$8AEFF797-845E-42A7-BD25-01DE0B2B6082","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1e97fba860600834744893195b828a33b233d941","datavalue":{"value":"0533.03024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789386$F128886C-1CB7-44DA-87AA-F4A36D19CCDD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"085cbadb6a1b25f38da62c0ed60d058ea6ab2c62","datavalue":{"value":"10.1016/0020-0190(83)90126-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789386$3106F80F-AE8A-4A74-B978-B901FB602060","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789386$DA7C4244-082B-44B7-B89B-90B387648CE8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q789386$ECC842A1-9512-4D8B-8A98-1960561B6F86","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bd7bae9b7b83230f77a30c3d2a47921838822c82","datavalue":{"value":"The paper gives some structural results on the class \\(\\Delta_ 2\\!^ p\\) of the polynomial hierarchy which hold if \\(NP=co\\)-NP. If so, then there exist sets in \\(\\Delta_ 2\\!^ p\\) that are neither NP-hard, nor in NP, nor in co-NP. Moreover, in this case it is undecidable whether a given set in \\(\\Delta_ 2\\!^ p\\) is in P, in NP, or NP-hard. The result can be generalized to all classes \\(\\Delta_ k\\!^ p\\) and is proved using a theorem published previously by the same author.","type":"string"},"datatype":"string"},"type":"statement","id":"Q789386$97391096-5740-4358-93F7-43362BA17971","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789386$1D2B1497-7ADD-42D6-AC6B-3478D8FF51BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789386$9B747482-BD91-4BCA-AFB9-930ED1E995A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6ee9f5484d11a01fb95552e5bea2154ebac0877","datavalue":{"value":"03D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789386$702A66EA-5D30-4F50-B86A-9CE4D49737AA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d5e5261f8b3455e77f2ab5e1b2342d98ad226784","datavalue":{"value":"3845568","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789386$36589095-8FC7-4F69-BF9F-C708C07896FF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q789386$E4FA9BAE-7322-4E21-8C26-887A218C5456","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q789386$3A07FFE2-003D-4DDA-8F70-2CE70FBB0289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"154ea0589dca3b50bef0f626c64f0e117c0eb521","datavalue":{"value":"polynomial hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q789386$32C79710-A388-4DEB-B861-949BAA925AE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d08b6a779dcb44e3d38fc6e628291b4c97c1e9b","datavalue":{"value":"NP vs. co-NP","type":"string"},"datatype":"string"},"type":"statement","id":"Q789386$E6029348-36A9-4E25-9B6E-25EDA73C339F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"98e020d336f4040f2344877fb27890751f480383","datavalue":{"value":{"entity-type":"item","numeric-id":1052096,"id":"Q1052096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789386$D1B045BD-6174-4E17-A5D5-79F39DF39C75","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0aa8d3ac5bbff6b41e0a3e53ebafb780beece760","datavalue":{"value":{"entity-type":"item","numeric-id":441885,"id":"Q441885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789386$4697B717-9479-4D1C-ABF1-0771BD26A3B7","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789386$312DD72D-465B-485F-BD70-79CEAF1E09C5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e266ff9fbbed1f3836fc91b83deac8898590e65d","datavalue":{"value":"https://doi.org/10.1016/0020-0190(83)90126-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q789386$D6BBAFD6-44A9-49C0-8E8A-0E87DB22A3FD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1893308ec15321c4ea1cbaaf7fd5adc1a7d80f69","datavalue":{"value":"W2057880543","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789386$9D813142-42AE-4A63-8FF9-179D0483EC2F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789386$D2E35CD1-ED66-47EA-AA1F-FB0601A6DBDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2654c1ad3008ab65ddf962a999d4d8045dcdea","datavalue":{"value":{"entity-type":"item","numeric-id":4085242,"id":"Q4085242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789386$CB4A5ACC-D4F4-4E72-9561-8E6DAE6D9DC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ece2270b16b9fbc48e0a9ac072c1cea045ecd584","datavalue":{"value":{"entity-type":"item","numeric-id":1162811,"id":"Q1162811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789386$D361D3E7-AE04-480B-9956-6BCC8496DD74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cefd7574d6776aa0391d0dd90bd375c1811d3f9","datavalue":{"value":{"entity-type":"item","numeric-id":1164414,"id":"Q1164414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789386$B6A385A1-3F90-491D-861E-FBF7F3671054","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31da41508378101a490da37864ec92d774ab823d","datavalue":{"value":{"entity-type":"item","numeric-id":4552753,"id":"Q4552753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcd334e8833d78208527dded8a5bc8cea79904c8","datavalue":{"value":{"amount":"+0.9160792","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789386$F50AC068-C835-4E64-89AC-7253D47404B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0fcb23a907eb115d302f3fa584bb80029bab035","datavalue":{"value":{"entity-type":"item","numeric-id":2781381,"id":"Q2781381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f963c2701c4cce91ff328a98c697a8c0aeed7532","datavalue":{"value":{"amount":"+0.8592202","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789386$510FDC18-74C4-45B1-A365-27D7160AEF65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f80975db1ed1156bb534327df3d07e37f1a3d405","datavalue":{"value":{"entity-type":"item","numeric-id":1773052,"id":"Q1773052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f30c9a47e3f698d75ea7347536f11e9e9c229e5","datavalue":{"value":{"amount":"+0.8507434","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789386$F9569451-D9CB-4DDD-84B1-10726A6723A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae0fbda85ca6616a137f4651403849c704f6f723","datavalue":{"value":{"entity-type":"item","numeric-id":4019409,"id":"Q4019409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e5c7c91a6338b3ae6dcc12d4dcf3a95aa1f804e","datavalue":{"value":{"amount":"+0.8435813","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789386$B6ED868D-C2BE-4CEB-988D-C42155FCFB8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3194c302aaa64ab4b50bf8bbf9d3f10eee50568d","datavalue":{"value":{"entity-type":"item","numeric-id":2896358,"id":"Q2896358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55bab97707580b3d5c0a3efda4e20ac53f1a6703","datavalue":{"value":{"amount":"+0.8375469","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789386$E114517A-D1DE-4D09-BBDF-4E29BA94E9F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7fdacd6691994ca513b39de45d3c3f090adf829","datavalue":{"value":{"entity-type":"item","numeric-id":4870931,"id":"Q4870931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07c947eb9e522395c8ee307129e0bd0489cba82c","datavalue":{"value":{"amount":"+0.8367057","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789386$D48997A4-5F3D-4E73-855E-C02B83E5556D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfbc748563bbd61862f0aefffa53aa4b80cdce50","datavalue":{"value":{"entity-type":"item","numeric-id":3336370,"id":"Q3336370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e20154ce0aa3e1879c0a0de4713617e9a3692dd","datavalue":{"value":{"amount":"+0.8358354","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789386$CC5FB86E-8040-4E2E-8C93-64547423134B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"380cc2b02635423a35e5e1cce5df9e7301b61d43","datavalue":{"value":{"entity-type":"item","numeric-id":343576,"id":"Q343576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5285814fa28eba4d0ffafe597b9c5de83ce834b","datavalue":{"value":{"amount":"+0.8346927","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789386$613CE923-4FEC-4EDD-AF02-47C6E5FB5F00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68f96cd620e495ce15c7412c5cc8fafca25b6116","datavalue":{"value":{"entity-type":"item","numeric-id":5929410,"id":"Q5929410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ec1c917d467868eb369431ffabb2cd836f5cbf0","datavalue":{"value":{"amount":"+0.83313143","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789386$0CECFF69-16A3-4C44-90BD-D36814B5FDB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f5e89614cdb5e8912b5c70b7678abbc1bc6b362","datavalue":{"value":{"entity-type":"item","numeric-id":3135731,"id":"Q3135731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6eb8497ce13a8460225ec7e80a9d886c482d824c","datavalue":{"value":{"amount":"+0.83303106","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789386$62E1C6E4-A30D-446D-BFE1-E5D8682058CE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the structure of \\(\\Delta 2\\!^ p\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_structure_of_%5C(%5CDelta_2%5C!%5E_p%5C)"}}}}}