{"entities":{"Q1199689":{"pageid":1210438,"ns":120,"title":"Item:Q1199689","lastrevid":69870564,"modified":"2026-04-13T10:53:45Z","type":"item","id":"Q1199689","labels":{"en":{"language":"en","value":"Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 94703"}},"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":"Q1199689$E4DCB2D2-371B-4A9F-922B-69671A4DD453","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"587a605dafa12cfc9566686284b0969023f09868","datavalue":{"value":{"text":"Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1199689$FD062046-FDE8-4B55-A2D5-6281CB6B9CE0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f5d8369d82fbd89cb6d1728256b7acb30f918224","datavalue":{"value":"0755.68050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199689$AC3D9D2C-CBFA-49B7-9DB9-6CB0F2E0802C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"69761a1dbc5646142f9cda3d9a96cc4ea4a08a95","datavalue":{"value":"10.1016/0304-3975(92)90232-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199689$FEF8DFEA-7F06-4F87-8488-6AFBEB6C3A6A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1787eb14bce43122c138b20ecca26156eee15dfe","datavalue":{"value":{"entity-type":"item","numeric-id":1199688,"id":"Q1199688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199689$DB3B931D-69DE-41C7-93C7-355251AB423F","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":"Q1199689$3AD3C431-9861-43C8-B1E0-173D79C37DEE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-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":"Q1199689$5364BEAE-CD61-4B79-A2EA-EDE2E700C71F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4081bdaa00f1e62e3559a17ce255f64863c7e411","datavalue":{"value":"Two classes of sets \\(C_ 1\\) and \\(C_ 2\\) are strongly separated if there is an infinite set \\(A\\) in \\(C_ 2\\) which is immune for \\(C_ 1\\), that means no infinite subset of \\(A\\) is in \\(C_ 1\\). Strong separations are shown, in a relativized setting, for virtually all pairs of classes of the polynomial-time hierarchy.   This paper combines several previously known nontrivial techniques (in a non-trivial way), essentially such steming from lower bound proofs for bounded-depth circuits (involving probabilistic arguments).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1199689$9CB4CAAF-A918-42B9-985F-A71ADCD6D216","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199689$CAB25CA6-35C2-4BE7-971B-3F9F5194E017","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199689$E9D578AC-C244-4889-AED3-6BD00EE6D76A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e808ca78327014217c99e9cda544c7cfa6855525","datavalue":{"value":"94703","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199689$72A6A3BC-BE0E-4D83-BB7E-76545B121E59","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06059c11269d258bbccac60c4e9a619d8f9e5b9a","datavalue":{"value":"relativization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1199689$27B7150E-95D3-4496-ACA3-197D8BEC1311","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"24390297a4214344743e183f68a0991ac2d156fd","datavalue":{"value":"strong separations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1199689$9984821F-7EA4-4B12-98C8-8AC5793F8FCB","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":"Q1199689$C14B86EA-D7FF-4844-BCAC-49B038122F3E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7049223383892a4fffd735cb4399a8b2dcb467b7","datavalue":{"value":"https://doi.org/10.1016/0304-3975(92)90232-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1199689$749541F3-2DAE-4DE2-A6EF-8704A6E88CC1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e009620c4edd25a61f6a804d08c09d99fea3c216","datavalue":{"value":"W1987726700","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199689$08076456-1B46-4F80-B0B5-40CBA8DD8C1A","rank":"normal"}],"P223":[{"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":"Q1199689$FA92114D-C5E6-4F06-B01A-86C44F991008","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"110c1e2c2af0807cf63aca7e44f16f8f618495f4","datavalue":{"value":{"entity-type":"item","numeric-id":1253656,"id":"Q1253656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199689$DD242AD2-AFA6-4EE6-8148-3F579DDD0A19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cffbf4f835aa5098d423c3d5d378b9a5e8d9619c","datavalue":{"value":{"entity-type":"item","numeric-id":3683534,"id":"Q3683534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199689$4D61F924-6A7F-4DE8-8430-D0577143FAF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd4f9b219f54da4cc88e481211745b7b70548f30","datavalue":{"value":{"entity-type":"item","numeric-id":4039803,"id":"Q4039803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199689$48225CDA-C511-4B2F-A66D-1D9E23B0EA83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bde708178fd22b5a6473ace4f76c9d9acbc0b80","datavalue":{"value":{"entity-type":"item","numeric-id":3347296,"id":"Q3347296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199689$5D199DE9-C213-40A6-AEC0-082E62B62DB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e39951d487d3bf563c62341ed381ea5be4f484","datavalue":{"value":{"entity-type":"item","numeric-id":3318683,"id":"Q3318683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199689$2FD143E9-C82B-4937-A16B-855DF9F8B9AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36336faac27edf7adb06de45895104a1a6b35c6e","datavalue":{"value":{"entity-type":"item","numeric-id":3331211,"id":"Q3331211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199689$CA5B76CB-280A-4D9B-A767-130B38691E97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2bcba6abf24137e5ea317e56b32f617a34d2b1e","datavalue":{"value":{"entity-type":"item","numeric-id":795829,"id":"Q795829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199689$60F473B5-CA9C-44A3-B047-97A916B4D3BA","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":"Q1199689$8C21A273-A306-4B2C-9658-FF02F2975D79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7288479262aed9deb41f23179ce1f042c08eb55c","datavalue":{"value":{"entity-type":"item","numeric-id":3479518,"id":"Q3479518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199689$6CA44814-801B-4785-B1F2-BED25528F4C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"917800fa52c098f2382f946c4094dc39e957bfbe","datavalue":{"value":{"entity-type":"item","numeric-id":4153600,"id":"Q4153600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199689$199534E7-9638-4B80-BBDA-FD759806B404","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":"Q1199689$E318938C-5102-4084-8457-FD7A1AADB32E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"932837bf2989ca9558ab1b005871e76cd52df763","datavalue":{"value":{"entity-type":"item","numeric-id":3751005,"id":"Q3751005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199689$002CCCDE-9194-40C4-A711-103F9FEAC475","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1204c3f34fada732e940dd3baf955a00f2804d4d","datavalue":{"value":{"entity-type":"item","numeric-id":1115610,"id":"Q1115610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199689$6A2FC2B1-2E16-473E-ADFD-70308301D685","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3065df023fcb2411980df376c6fc4777f5d291a5","datavalue":{"value":{"entity-type":"item","numeric-id":1241440,"id":"Q1241440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199689$4C46DA65-AA80-4601-BC36-989047009FE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54e3771f8171656e0aed45bf0777afe8aad7a3a9","datavalue":{"value":{"entity-type":"item","numeric-id":3902480,"id":"Q3902480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199689$1B41BF2E-AE97-43EC-9A99-ADD3E3E58818","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"111f565a4c91ebac8f533311352716a2f6aeaee4","datavalue":{"value":"Q126989242","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199689$20EC01B7-1EFE-4235-8D86-D74A9B19058E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47f413e04dca08b8ef7b87382cc780b7264f941b","datavalue":{"value":{"entity-type":"item","numeric-id":3816982,"id":"Q3816982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27dcbc0a98aaa26a21b0caa1ec697e915c224b9b","datavalue":{"value":{"amount":"+0.8820592761039734","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":"Q1199689$A7EBF10A-B499-4D8D-9CBB-9BBC22D815D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"748501335acff12490f9a152aa65f432e970205b","datavalue":{"value":{"entity-type":"item","numeric-id":3479518,"id":"Q3479518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"675d701a1fda08e787802db05193b5685f08da56","datavalue":{"value":{"amount":"+0.8315902948379517","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":"Q1199689$87A7694D-3B9C-4149-8ECC-82FB0DC50E13","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":"8a56239724b276cde3bb5648f1bb4cbeccc825ce","datavalue":{"value":{"amount":"+0.8276253342628479","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":"Q1199689$BEA740BF-979D-41BC-BA5A-B1B0B084124F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8037b0c0efa78139badd5affa6856ba09040299f","datavalue":{"value":{"entity-type":"item","numeric-id":1898109,"id":"Q1898109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b068d08689fbfad62ea7076fd8ba4ba7da283bd1","datavalue":{"value":{"amount":"+0.8204677700996399","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":"Q1199689$ADEC43AC-A503-4D10-9608-99A91417B2AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b510d2a016c1f7e009ea6232455bf436060ba80e","datavalue":{"value":{"entity-type":"item","numeric-id":4729769,"id":"Q4729769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b3f2945afefe102d67ed9e6331faa92234a8cc7","datavalue":{"value":{"amount":"+0.8188956379890442","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":"Q1199689$54554149-9CFA-4063-9CEA-FF110B25270E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Strong_separations_of_the_polynomial_hierarchy_with_oracles:_Constructive_separations_by_immune_and_simple_sets"}}}}}