{"entities":{"Q1111385":{"pageid":1122134,"ns":120,"title":"Item:Q1111385","lastrevid":49223869,"modified":"2026-01-06T19:26:41Z","type":"item","id":"Q1111385","labels":{"en":{"language":"en","value":"On sparse oracles separating feasible complexity classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4076623"}},"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":"Q1111385$94D4B2BD-07D7-4C60-B0EB-D2F798554223","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b1f8fbe6a2735fb9c3f867e4684dd25156179d79","datavalue":{"value":{"text":"On sparse oracles separating feasible complexity classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111385$3DA079AD-8C56-4696-89CB-763FD385A3A9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cfee70dcdee5ba43adfb788adeac22051f85c0a7","datavalue":{"value":"0658.68055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111385$D8EEB656-0836-4670-BC71-FF66F30DAD05","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a3b2cf77c6399506803b1e09291ab91332836e8c","datavalue":{"value":"10.1016/0020-0190(88)90176-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111385$9B722AFC-A944-4E10-81D3-3D4D43D8D249","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f24581060e1fc674d2a5c7705dc19743c7374ca5","datavalue":{"value":{"entity-type":"item","numeric-id":1071499,"id":"Q1071499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111385$565045DF-DEB3-41B0-B55F-D80DCDF50CC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"95d207a16ce6533a2e03f4685944467ead41f45c","datavalue":{"value":{"entity-type":"item","numeric-id":161382,"id":"Q161382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111385$426CF193-5F1C-4308-9B65-7BF0671F3C0E","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":"Q1111385$D9DDDF13-EC0A-423A-ACE8-8017D93BDE99","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1111385$06916B4A-2DCC-4516-835B-4416D56633A9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"28f1e3250f2ff126f5c53d2db15a6aa0419b3d55","datavalue":{"value":"https://hdl.handle.net/1813/6547","type":"string"},"datatype":"url"},"type":"statement","id":"Q1111385$6EBBB251-474D-40A3-9507-598CE89B0E69","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"36c09d01ff457bdbb62175d156ef121f8b3e1d4a","datavalue":{"value":"This article clarifies which oracles separate NP from P and which do not. In essence, we are changing our research paradigm from the study of which problems can be relativized in two conflicting ways to the study and characterization of the class of oracles achieving a specified relativation. Results of this type have the potential to yield deeper insights into the nature of relativation problems and focus our attention on new and interesting classes of languages.    A complete and transparent characterization of oracles that separate NP from P would resolve the long-standing \\(P=? NP\\) question. Here we settle a central case. We fully characterize the sparse oracles separating NP from P in worlds where \\(P=NP\\). These separating oracles are exactly the non-self-printable sets. Equivalently, they are the sets of high self- referential Kolmogorov complexity. We prove related results about co-NP and PSPACE.    [Cf. also the author's article with the same title, Lect. Notes Comput. Sci. 210, 321-333 (1986; Zbl 0605.68034).]","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111385$E10E686F-EC22-4DD0-9150-6F69B5784CA4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111385$1E3EE045-7018-42DD-BBD1-D51CCE83AE57","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6faea1ab298f26bc3d4b6d08555c16c905948102","datavalue":{"value":"4076623","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111385$DF9919C3-EC58-4FB0-8114-A508D3103F1A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e4fcb22762b57295d3b8e25286b7cfc2182e721","datavalue":{"value":"P-printability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111385$5938E2F6-A9E8-4164-98BB-2699E4A4C928","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"319f7aef6d48907b019428ced327b73484cf6132","datavalue":{"value":"polynomial-time hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111385$6E85EB60-BD5F-4459-8BD1-FA4508E71A1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b302eea3c175051b08ae21ed3ffc354cb887962","datavalue":{"value":"sparse oracle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111385$4FB8A5D5-AB6A-4FAB-B655-4083B54E0E3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e72e049bc237dae86b089c5973d4b3774835224d","datavalue":{"value":"relativation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111385$E1F1E7DC-AB2A-4EAA-A1C4-D34C50F1BC7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2fbb2e9d154ceb175756c19a9cc042a97d1c430f","datavalue":{"value":"classes of languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111385$0577912C-8758-468E-A251-DDC13A8A70FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"662fcbaebead171347d76c0b4c2603e151e8eff5","datavalue":{"value":"separating NP from P in worlds where \\(P=NP\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111385$06538459-F679-41A1-9318-FB3584E8DA2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e343c0d066d632a0b869d2dadad72cc8a3999e1","datavalue":{"value":"Kolmogorov complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111385$A07797C9-5ACD-4D77-8F61-6907B1159932","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":"Q1111385$12CE740B-0DB3-46F7-B556-0D0789F7D4CE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b23e9277e1823abe9291316bb2c8a515637bdcab","datavalue":{"value":"W2088269446","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111385$0811922A-5FCE-4CFA-9C9F-497033BA0BC1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"560bf61b4d356df20b0e62b14b1ce453301159dc","datavalue":{"value":{"entity-type":"item","numeric-id":3747725,"id":"Q3747725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111385$7AC96B76-83E1-4136-A53F-E5D822CE5DFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c4b58f9e8478a4210509de111b81e4ccd911506","datavalue":{"value":{"entity-type":"item","numeric-id":4086709,"id":"Q4086709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111385$1703C3C2-AE08-4837-8ED9-67125B4FEBD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40ff498ff7e5d4e1f1b7369800801ec2027c1bf0","datavalue":{"value":{"entity-type":"item","numeric-id":3740234,"id":"Q3740234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111385$B97F752A-9205-44F6-A16B-04E808FA0ECD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab0bbeb503b6269a452e86ee83e6a8c71fdfdfd0","datavalue":{"value":{"entity-type":"item","numeric-id":3734382,"id":"Q3734382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111385$B513CC6F-F9DB-42B4-8C48-0202F859E29E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a3697b53f1f4a9ea7f20b029202a3736aaeaef8","datavalue":{"value":{"entity-type":"item","numeric-id":3742716,"id":"Q3742716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111385$79820DC2-49C6-4678-9FAC-D18B4CF3F075","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c25925be7f5c292edb63efdcdcacb15993e69254","datavalue":{"value":{"entity-type":"item","numeric-id":1348523,"id":"Q1348523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111385$8082BB2F-DE15-4E35-A32F-2DA4E36CC2CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111385$554BA9E5-1D67-4EC3-8053-54925B7690B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36228870059a5f0f90df014e35180ed7c6a65ec9","datavalue":{"value":{"entity-type":"item","numeric-id":1086557,"id":"Q1086557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111385$2AD20074-C86E-4522-B0A9-3A8BA74575B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db9b560480f120973173b330c8c9be495fdaffb9","datavalue":{"value":{"entity-type":"item","numeric-id":1073788,"id":"Q1073788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111385$4A3557C5-E35D-48AF-B170-1D364437E771","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"105101dba9c28fafb7b0ccbfd4eb7b9c22c79810","datavalue":{"value":{"entity-type":"item","numeric-id":3343440,"id":"Q3343440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111385$9837ED5F-D4D6-44C0-BC1C-281FBAB8BD68","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79ea52b61baa8be7098d58f3021d1fbf7fef6d27","datavalue":{"value":{"entity-type":"item","numeric-id":3742716,"id":"Q3742716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30f55ac3b520779998906b145c2b6547592bbf49","datavalue":{"value":{"amount":"+0.9707416892051696","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":"Q1111385$5C87D2D2-2E6D-4655-AB2F-C5D661E7C801","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"909e21571ee0aa44b4ee0c474aece50eed2f2784","datavalue":{"value":{"entity-type":"item","numeric-id":3691647,"id":"Q3691647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a17cb5040d51dbcdb5f330ace661bcffe3aa7c0e","datavalue":{"value":{"amount":"+0.8443164825439453","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":"Q1111385$0E9C22D5-F428-43B1-840D-31B351DD2994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3dac3c072741a3da1707fc78141312a1fbda7ff9","datavalue":{"value":{"entity-type":"item","numeric-id":3808082,"id":"Q3808082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c045c842095f6b37a8f126742e2015e4b2d947d2","datavalue":{"value":{"amount":"+0.8337470889091492","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":"Q1111385$E5D2216E-8FDC-4F94-ACB3-C2A0F73B762D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9728d403cc609a50fdf1731c9f20f1755fa93145","datavalue":{"value":{"entity-type":"item","numeric-id":1894447,"id":"Q1894447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea553a79daa64ded6db3c7f382d5ef53c7a73bb1","datavalue":{"value":{"amount":"+0.8201082348823547","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":"Q1111385$967C0E99-6117-4B5E-A0C7-5F128FE83276","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5860284554d2167247a9abfd9beb9dbb00ec9ef6","datavalue":{"value":{"entity-type":"item","numeric-id":3811709,"id":"Q3811709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a991cb2ca6e64283666cb9636091a6bea113669","datavalue":{"value":{"amount":"+0.8185222148895264","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":"Q1111385$E1B1D2C7-72C5-4D55-9886-2F573514B819","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1111385","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1111385"}}}}}