{"entities":{"Q908700":{"pageid":910548,"ns":120,"title":"Item:Q908700","lastrevid":49353178,"modified":"2026-01-07T00:35:28Z","type":"item","id":"Q908700","labels":{"en":{"language":"en","value":"\\(P^{NP[O(\\log n)]}\\) and sparse turing-complete sets for NP"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4135400"}},"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":"Q908700$EFF6B7AA-7DC9-49D9-9FD6-A31AE16E58C5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b9047f0b58ed8dd9e7bdc4f3902dacb7d7579cf2","datavalue":{"value":{"text":"\\(P^{NP[O(\\log n)]}\\) and sparse turing-complete sets for NP","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q908700$16E0E23E-6E49-4813-A52F-53BB77FDA452","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"67a60a36109e0c604e85f3e7ad2057105293dc14","datavalue":{"value":"0693.68027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908700$68EF47FA-A139-4C59-807F-6EF08B861830","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2988dfa195474da9e06e2b61356e6e063f9b9373","datavalue":{"value":"10.1016/0022-0000(89)90024-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908700$9E989811-1AF2-42ED-AE4F-F3EEA2CE0498","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"71e1234a48cbf78dc4291aeaf4e18bd4e9ce5696","datavalue":{"value":{"entity-type":"item","numeric-id":908699,"id":"Q908699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$FBFF28FA-FA50-42BF-95CD-545FB70E0E64","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$DE81783A-B31D-4D27-88C2-7DA63E9114B8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q908700$044606F6-45C2-467B-A559-8683BBAE9F15","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2f04bbf9bbbecc85c13979cfae100ba35fa67ff3","datavalue":{"value":"It has been known (\\textit{S. Mahaney} [J. Comput. Syst. Sci. 25, 130-143 (1987; Zbl 0493.68043)] that the polynomial hierarchy collapses to \\(P^{NP}\\) if NP has a \\(\\leq^ P_ T\\)-complete sparse set. The author improves this result by replacing \\(N^{NP}\\) with \\(P^{NP[O(\\log n)]}\\), where this latter class is the class of all languages acceptable by deterministic polynomial time machines making only O(log n) queries to an NP-oracle. This result is a consequence of the following one: If for a sparse S in NP it holds that \\(coNP\\subseteq NP^ S\\), then \\(PH\\subseteq P^{NP[O(\\log n)]}\\). This collapse result is optimal in the following sense: For any function \\(f(n)=o(\\log n)\\) there exists a set B for which \\(NP^ B\\) has a sparse \\(\\leq^ P_ T\\)-complete set and \\((P^ B)^{NP^ B[O(\\log n)]}\\subseteq (P^ B)^{NP^ B[f(n)]}.\\)    Furthermore, the paper exhibits \\(\\leq^ P_ m\\)-complete problems for \\(P^{NP[O(\\log n)]}\\) and discusses conditions fo the class of languages \\(\\leq^ P_ m\\)-reducible to a set C to be equal to \\(P^{C[O(\\log n)]}\\). For \\(D^ P=\\{X\\cap Y :\\) \\(X\\in NP\\wedge Y\\in coNP\\}\\) it is shown: If \\(D^ P=coD^ P\\), then \\(P^{NP[O(\\log n)]}\\subseteq D^ P\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q908700$6EB8D5DD-8185-43FF-9C47-13EBB0CA50A8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908700$5095F9AA-9FEA-4D58-937C-1A9A0A09DC45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908700$3B041CC4-B1BA-42B6-936B-D98C9DAE440E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908700$6B2C3540-D929-4094-BD49-F8601D2F8747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908700$3173BDE0-E0B7-461B-BFE5-ED1D2FDD1755","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908700$AF73FD59-4353-4C4C-BC1D-B76B6BB3FCFA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a944ed2f6ec429936c933add0d3521147c5beac7","datavalue":{"value":"4135400","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908700$793ADDA3-0490-4006-87DB-26937E633E1F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b9d868a2063d15cbc5545d9ca7928353602414d","datavalue":{"value":"sparse complete sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q908700$166F6362-B11C-4279-9C9F-BB386CEDA666","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51a081451adcb2a15e149b804f956881070acef6","datavalue":{"value":"query restricted oracle use","type":"string"},"datatype":"string"},"type":"statement","id":"Q908700$17306930-01FC-4D58-9527-E4C2EE72EABA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c2cd92410cb6f5e64e892d5676dd1461f28bf7c8","datavalue":{"value":"collapse of the polynomial time hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q908700$8510C22B-F29B-4603-858C-A521D3D31806","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22ebdbb75f88b26b2f854a77b4dd164319f78c13","datavalue":{"value":"NP optimization problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q908700$47F596DE-3B02-4B66-8F2C-73627A651B0D","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":"Q908700$7A3CA8CB-0813-4AC7-A96B-17122F5710EA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"45543575358fa9f936229ea1980f01498db37989","datavalue":{"value":{"entity-type":"item","numeric-id":4128010,"id":"Q4128010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$B847D0EC-53F0-47AB-9841-08C1749B713B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c317ee9b89d25866849eff84487be5a7c7991b60","datavalue":{"value":{"entity-type":"item","numeric-id":3331209,"id":"Q3331209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$23FBF88E-2361-4DA6-B9C9-40C1858C4BB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bcb11f0b30802ff1fa8b04ab34822dc12429034","datavalue":{"value":{"entity-type":"item","numeric-id":3832042,"id":"Q3832042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$ED734AA8-368F-4FA9-BC70-3FA9CFCC9D49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f06e660485cbc895c0095c4f085a34cde29ca5c0","datavalue":{"value":{"entity-type":"item","numeric-id":3765250,"id":"Q3765250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$743E36DA-826E-45E4-9011-F8B2AAD17192","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80da5dbf79d1c137536de30a44e307449b537460","datavalue":{"value":{"entity-type":"item","numeric-id":584250,"id":"Q584250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$47839BE3-2FFC-415F-9D49-22748B02284E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$D8521E86-4337-4534-9446-F91281DC92C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d429f380799f6c0c15be647230cd0a7ab6a20061","datavalue":{"value":{"entity-type":"item","numeric-id":1822968,"id":"Q1822968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$9FF2549D-6482-4309-9F35-AEE05986166B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b2a1a71b49ec8a49d1aaa20916821b36ece12fa","datavalue":{"value":{"entity-type":"item","numeric-id":3815290,"id":"Q3815290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$ABC93C21-DEAC-45A1-ABE7-76F163EF549C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4cded707123398ff6798a322d45de37a4390f5b2","datavalue":{"value":{"entity-type":"item","numeric-id":787674,"id":"Q787674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$A8426824-5F95-45C6-8572-6827A2CF2251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c30f6e432ce9e9ae75031144ac1199e0b83ca0d7","datavalue":{"value":{"entity-type":"item","numeric-id":1107309,"id":"Q1107309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$FC7ECC16-2D07-4D6F-820D-106DED0D4DFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7d15acf9b2dc594da15dc289088a8a93d59b4f8","datavalue":{"value":{"entity-type":"item","numeric-id":1223166,"id":"Q1223166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$7BA0A8F6-6EC5-4FC5-A0F3-93C9279427F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c62de5048fa954af00b82660416a315c8b87034","datavalue":{"value":{"entity-type":"item","numeric-id":1164997,"id":"Q1164997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$2F44B9C1-ADD0-4F5F-A479-CFC7C67579B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6139d2fb76790fbc1a2ff20446f11785d8f1488","datavalue":{"value":{"entity-type":"item","numeric-id":1168733,"id":"Q1168733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$AE9BD934-555E-4F95-A528-F94F5E2273E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32c9cf122d104d7332be7d6610d7ce2681b03b64","datavalue":{"value":{"entity-type":"item","numeric-id":3768398,"id":"Q3768398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$D61E7B4A-D485-4863-8294-AFF8F4990669","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"800321fe9f6efe205a2eb283e0da5841a2b5eaad","datavalue":{"value":{"entity-type":"item","numeric-id":1061485,"id":"Q1061485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$1D9BD84E-B4EC-44FF-8E79-39E1EA611A04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53e31dd483387e2770ec0ec431458678950cd036","datavalue":{"value":{"entity-type":"item","numeric-id":4743737,"id":"Q4743737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$10BF6309-E098-4E69-85ED-9808BE30D8F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$81000FDA-4350-40EF-B786-D8EDDE5C45C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f6be2378be9ef718165d6decb820a8d040ba744","datavalue":{"value":{"entity-type":"item","numeric-id":3766851,"id":"Q3766851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$069A3123-01E7-4831-8AFF-43D1ABDF629B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d1f5d749e4775b9ff8ad70d19f88e3741e680ea","datavalue":{"value":{"entity-type":"item","numeric-id":3495646,"id":"Q3495646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$3960B23D-C76A-45E4-99FC-603F55B86C66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f527009870fcf7573f42d3f4f5039928a6728916","datavalue":{"value":{"entity-type":"item","numeric-id":1069299,"id":"Q1069299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$0C31CFFC-6F82-47E6-9A6B-6ED673CF1E2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ef86d27229f88234625ab5cf631770a7bacc164","datavalue":{"value":{"entity-type":"item","numeric-id":794427,"id":"Q794427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908700$49DB8921-699A-40B9-8BDC-9F140C667CFB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a4360a93bcbc3394988b9c0cc760fa26a439de0","datavalue":{"value":{"entity-type":"item","numeric-id":3811710,"id":"Q3811710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ae8a55c29eb736f27ef150afc57cd4304af1063","datavalue":{"value":{"amount":"+0.8735564351081848","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q908700$3CDFDF74-BDA1-4B06-A20E-755400262C5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c2adc893ba0e353cc07a8405075284e7651ff53","datavalue":{"value":{"entity-type":"item","numeric-id":3335768,"id":"Q3335768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1213b74fdba74d4865d3f6d99396f942aff65ae","datavalue":{"value":{"amount":"+0.8497106432914734","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q908700$3939621C-4FAD-40FF-ABC3-C09A578FB3B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d2c6b00319aebd8229b2a325bdd25c903fad5ba","datavalue":{"value":{"entity-type":"item","numeric-id":3314997,"id":"Q3314997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3a55930b1bc82eebfe80a0db496da6d125a92d0","datavalue":{"value":{"amount":"+0.8434813618659973","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q908700$567564F3-CC6D-4A68-9046-87502EBCA7A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd85a7c73f26045793f0cbd414904cce05f9bea5","datavalue":{"value":{"entity-type":"item","numeric-id":3028343,"id":"Q3028343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51d7defb4c8dd34c115e61b8b8c2b5cd14456ce2","datavalue":{"value":{"amount":"+0.8357599973678589","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q908700$C65CA902-0C4B-4C82-9767-EE8A6609FE28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e15b996c276ccc4ba58ba0871d17ffb6b8ab2eb7","datavalue":{"value":{"entity-type":"item","numeric-id":3346297,"id":"Q3346297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ee4f4c5468e9a61aa5e96bcd6d8abd67103454d","datavalue":{"value":{"amount":"+0.8343797922134399","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q908700$EAE39FE2-B824-4AC3-9CB5-4CBDA29FF745","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:908700","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:908700"}}}}}