{"entities":{"Q1261468":{"pageid":1272218,"ns":120,"title":"Item:Q1261468","lastrevid":80282942,"modified":"2026-05-06T15:50:28Z","type":"item","id":"Q1261468","labels":{"en":{"language":"en","value":"Hard promise problems and nonuniform complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 404985"}},"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":"Q1261468$649B2C03-2483-4FBD-8BE6-E32E37A83990","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"487971095cff828995ce116963df49f0a245be41","datavalue":{"value":{"text":"Hard promise problems and nonuniform complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1261468$B9E6B026-7805-4A72-A4DF-AF187E862C27","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b16e2d15fb1f0a589733e55d50017239be69df37","datavalue":{"value":"0778.68035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261468$62138ADB-2648-43BE-BAF8-7AA1F1093F9F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2ef11b4a03a2f27a83a1116317c244577cf847d5","datavalue":{"value":"10.1016/0304-3975(93)90120-I","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261468$97806671-01A1-43CF-9C09-7D23456650BE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"23227babb520a0fe322bb349932c7f9652e74c57","datavalue":{"value":{"entity-type":"item","numeric-id":293303,"id":"Q293303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$53FA47A4-3DD6-4894-B185-5BCBB79BF619","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"29b02350197f27ae1879c4b07e2f60550fcfbf54","datavalue":{"value":{"entity-type":"item","numeric-id":161380,"id":"Q161380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$C1E85951-821F-45E8-B79D-247A532CE8B2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$03C211E8-E925-46C7-B98F-AB45C91E9FC1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c4a0b6e2eb88a0201332122fd35e1ce2d966cc96","datavalue":{"value":{"time":"+1993-09-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1261468$F217DC33-2982-47B8-B48F-C6C554ADFFB9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e7b7c679467ba7453b1fc15521b5712418bb526f","datavalue":{"value":"The paper contains relativizations and generalizations of classical results of \\textit{K.-I. Ko} [On self-reducibility and weak \\(p\\)-selectivity, J. Comput. System Sci. 26, 209-211 (1983; Zbl 0519.68062)]; \\textit{K.-I. Ko} and \\textit{U. Sch\u00f6ning} [On circuit-size and the low hierarchy in NP, SIAM J. Comput 14, 41-51 (1985; Zbl 0562.68033)]; and \\textit{J. L. Balc\u00e1zar}, \\textit{R. V. Book}, \\textit{U. Sch\u00f6ning} [ The polynomial hierarchy and sparse oracles, J. Assoc. Comput. Mach. 33, 603-617 (1986; Zbl 0625.68033)].   Some of the results might become more perspicuous if the hypothesis ``\\(B\\) is a solution of \\(PP-A\\)'' is replaced by ``\\(A\\) is \\(p\\)-selective relative to \\(B\\)''.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261468$7A744145-30A0-4102-AEE3-04F081F5F791","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261468$AFFB3696-2848-4DF2-A71A-317392A41E1F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"697bd438f3a74c496d1a5d071193e9e843b496cd","datavalue":{"value":"404985","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261468$5AA93497-2BAB-4449-808B-A78FA98CD6BE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6daeae184d5daea94a71d00cea7904586210d46","datavalue":{"value":"\\(P\\)-selectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261468$5BF2A578-B002-4EFE-BB31-E5C3138CE41C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0bf39ff67c734ccef72308ae15736ee44ba84c0c","datavalue":{"value":"self-reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261468$E867735D-DE61-4FF2-A17D-9E814A291634","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a4571ef153b923cfe613550c3ec4d2c1e665f8c","datavalue":{"value":"relativizations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261468$FF52F0CA-598A-4362-BBC4-12B3BFD0EC43","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9c446a25cf0b963435717eedcea7753bd22a49ba","datavalue":{"value":{"entity-type":"item","numeric-id":960465,"id":"Q960465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$B0999E98-17C5-40F1-810E-10E09111B489","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":"Q1261468$8CCCA884-5791-466B-8ED2-2A6734516757","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"670ea104a6030c36d2d05eac54cafcbfe57477ff","datavalue":{"value":{"entity-type":"item","numeric-id":1263281,"id":"Q1263281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$85D31178-773A-4447-AF10-4A77EE79806B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20dbb88399b28648dc9d78bc8b7f00777d16b9fd","datavalue":{"value":{"entity-type":"item","numeric-id":3028343,"id":"Q3028343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$DEAEA051-EEDD-4AEF-9C66-F66CD0DD1E07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c2468561c612bfca6312de0928b48a059a609c8","datavalue":{"value":{"entity-type":"item","numeric-id":3758244,"id":"Q3758244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$8E835E3D-E047-49E0-B80F-C5710AFDDD3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49ee1410bd306d6722cc2c176479c826bbb0715d","datavalue":{"value":{"entity-type":"item","numeric-id":3722415,"id":"Q3722415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$E9563215-E8AE-486C-BE37-8DF967997BA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d8481b383524bbb1d42d352020c18ea39581b9e","datavalue":{"value":{"entity-type":"item","numeric-id":3888962,"id":"Q3888962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$8CC1C830-7234-448B-B3E8-1F9A41B5FF66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca8e2226bc49403f5d34bedd57297744e386790","datavalue":{"value":{"entity-type":"item","numeric-id":1168215,"id":"Q1168215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$2D28D893-2B23-4C88-ABA9-0C23634D3309","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1aa96b7c0ec9bc7a683e7636e258c3fded01e42","datavalue":{"value":{"entity-type":"item","numeric-id":3787917,"id":"Q3787917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$DBC1BD0C-DE9D-4AC1-8A17-5E25C2F62F6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6bef531e3c54b91b631aa952c0ca63f0ac7db19","datavalue":{"value":{"entity-type":"item","numeric-id":1054475,"id":"Q1054475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$C911CD6C-4491-4DE7-A827-633320A389C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b543b24a2524e76130d5c1525baa40aa9abdeef","datavalue":{"value":{"entity-type":"item","numeric-id":3675520,"id":"Q3675520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$7094FD92-76F3-4022-A8D2-6EC0C6A49F5A","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":"Q1261468$26A9750D-9F0E-4EA5-A7D1-216F7B7A668E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a098647e2133258d563151bef051aaad7f30f8b","datavalue":{"value":{"entity-type":"item","numeric-id":1055405,"id":"Q1055405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$C475AC4A-B316-4F44-8A77-AAC271249051","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a830cafef1f2c438cb7e2286bda476de992419e","datavalue":{"value":{"entity-type":"item","numeric-id":1052097,"id":"Q1052097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$20DD86E7-BD2B-4E06-A6F9-C976D39313A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b66204a7ac5420fb2081d1faeebb9954b727cf5f","datavalue":{"value":{"entity-type":"item","numeric-id":3731587,"id":"Q3731587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$43B1FDD9-4CAB-44F7-8D3B-FED4C18311A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7ab90453baf406aa3f7c8428f867542de4b82f1","datavalue":{"value":{"entity-type":"item","numeric-id":5636865,"id":"Q5636865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$33A276B7-6A06-4468-AECE-82A028017F96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37bd93f050a29505d9954e41ab03268b153e49a7","datavalue":{"value":{"entity-type":"item","numeric-id":4190619,"id":"Q4190619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$683E2ACE-CE46-4609-8BC5-52DF8161661C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd520b49bc58e84d7c227fcb0bc974b432f91cc2","datavalue":{"value":{"entity-type":"item","numeric-id":1166515,"id":"Q1166515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$B1B63C1F-4EE7-47C8-B681-071172DDCE59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"317fac275ee29f42a5ca834b66c5ee7f076c89cb","datavalue":{"value":{"entity-type":"item","numeric-id":1109568,"id":"Q1109568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$D3EDA5DC-BE3B-47CF-BCB8-8EBA0B1E9785","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1dfd82bed9266a9eb9ee03c49c86a8c45cb2436","datavalue":{"value":{"entity-type":"item","numeric-id":1090454,"id":"Q1090454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261468$16FC238E-F5E5-4096-855A-5EB62EEA7A70","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"808b70f408b84029ae247f92dac9fd822945ea18","datavalue":{"value":{"entity-type":"item","numeric-id":3975932,"id":"Q3975932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec44982ea60f708291b08ddacf54d90e8faa5e2e","datavalue":{"value":{"amount":"+0.8669263124465942","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":"Q1261468$A4CC66BC-E1CB-4756-8D51-5CB1454B408D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af709387fcfba056696de4de80236ba9dd1d0868","datavalue":{"value":{"entity-type":"item","numeric-id":3765753,"id":"Q3765753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a46378e78ea8fc907b64f8f0683bde6df56142c","datavalue":{"value":{"amount":"+0.8661763668060303","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":"Q1261468$D63686C6-908C-4207-9CB0-D242F3CA52AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23c5651a461496335ca71ca1c50042685b0e792a","datavalue":{"value":{"entity-type":"item","numeric-id":1109568,"id":"Q1109568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"812655c226e46c0c7bb62f50c35f6cb9d686b242","datavalue":{"value":{"amount":"+0.7980728149414062","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":"Q1261468$93F09107-45E1-4CEE-A0F0-9F2F18820101","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f73a2f614914ac732f7283bda95dff7d1861ee9","datavalue":{"value":{"entity-type":"item","numeric-id":4877117,"id":"Q4877117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61e9ee7a782e50d4b1ba05ee68e0158c67290c31","datavalue":{"value":{"amount":"+0.7743775844573975","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":"Q1261468$941416D5-931E-40C5-AF69-2245B3DF006B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a2b71834e9198e229d0437378a17fb7c6ec2580","datavalue":{"value":{"entity-type":"item","numeric-id":4504560,"id":"Q4504560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61e9ee7a782e50d4b1ba05ee68e0158c67290c31","datavalue":{"value":{"amount":"+0.7743775844573975","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":"Q1261468$94C63819-42FB-40A5-AF97-99C90A1B2176","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Hard promise problems and nonuniform complexity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Hard_promise_problems_and_nonuniform_complexity"}}}}}