{"entities":{"Q2638773":{"pageid":2649516,"ns":120,"title":"Item:Q2638773","lastrevid":44545050,"modified":"2025-11-23T19:11:41Z","type":"item","id":"Q2638773","labels":{"en":{"language":"en","value":"Separating the low and high hierarchies by oracles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4182812"}},"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":"Q2638773$A12FF927-261A-4EC0-A1AA-2D9EF9702DCD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f5467a1083fb892d4277bd0fe308af3fbfb9dff1","datavalue":{"value":{"text":"Separating the low and high hierarchies by oracles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2638773$CD65BECF-FD50-4C24-8096-5F336D475447","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"72745ac7315ea348b827f7964f40130470a1df35","datavalue":{"value":"0717.68033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638773$1CA522BD-4E33-4B28-90AD-9BCB70EA4F3D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5626de2a57f37ec5eafd3cc493b190cdc86bdb18","datavalue":{"value":"10.1016/0890-5401(91)90002-J","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638773$2EBD36C6-0E28-4A24-8809-A3072CA5471B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638773$BAE5A467-86DD-434F-ADED-1C356BA4DE56","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q2638773$27983CC1-B4CE-4AAE-A6F9-8D901B8A7571","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"842c601dad2aee392e2a7d77e2661a3df8eb92e7","datavalue":{"value":"The low hierarchy is an infinite sequence of classes in NP that starts with P and generalizes the notion of ``easiness'' in NP. The high hierarchy similarly generalizes the notion of ``hardness'', i.e. NP- completeness in NP.    The author shows that in a relativized setting (i.e. permitting oracles) an oracle A exists which forces the low and high hierarchies relative to A to be infinite.    Furthermore, for each k an oracle set \\(A_ k\\) exists which forces the low and high hierarchies to have exactly k levels.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2638773$8EBB6350-8C24-43F5-A23A-838771E68AD4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638773$D9C1A32C-E16B-4F09-A9C3-A32B3513050D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638773$A5855B6A-3A27-44C8-A5B9-F40780CACBC3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a307d537dfcff2a4a9c24ed12f25816cd298cbf8","datavalue":{"value":"4182812","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638773$1FF15861-2235-4867-A9B7-BE8E2875D137","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c912dd45456959aa9594fa8a89e3f787ad398ae","datavalue":{"value":"oracles","type":"string"},"datatype":"string"},"type":"statement","id":"Q2638773$75501B96-9EC7-4C7C-B85D-276D5F84079F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48e1877f07a2e0908de5bb6b8f6c2025e2611367","datavalue":{"value":"low hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q2638773$805DC076-FAE1-4B56-B124-D54D62E11472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6dd7f7e4e95e71c9c3362a8f7da63d25d50f5ff","datavalue":{"value":"high hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q2638773$142B55C1-5D45-4194-BEEB-977821AE53D5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"13bc86079a0769c5ab1c6f28dc4e52a39f4a573a","datavalue":{"value":{"entity-type":"item","numeric-id":1295380,"id":"Q1295380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638773$614F7D16-1D55-4256-BA37-EBDBC75616F5","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":"Q2638773$23B68169-DF39-49AA-A579-5BAAF1AA8405","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":"Q2638773$DB58BD8B-D702-4610-BC91-C2315D977905","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":"Q2638773$6277A628-8488-42A0-BF07-B3EFBE8A2BDD","rank":"normal"},{"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":"Q2638773$FB33AC03-7953-4DE1-B247-25CE6D3BAA1C","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":"Q2638773$4401849C-38AB-4C8D-97CA-E458CE9E9A3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cfa66b5371e2888d25cb2bc33aedb7868119dc8","datavalue":{"value":{"entity-type":"item","numeric-id":4729353,"id":"Q4729353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638773$9FF634E9-5E7E-4005-9006-7AFB55A0DA1D","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":"Q2638773$12FCEEEF-8D54-48E7-B42F-E84B6F3079BB","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":"Q2638773$9EAEF7B3-F37E-4ADA-AEB8-FB23658A5087","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":"Q2638773$F837F462-0C9C-44D4-BDCD-DF371C816A7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a69d483c2e0de51dd3c43ba8acfd980a2417bcf","datavalue":{"value":{"entity-type":"item","numeric-id":3758245,"id":"Q3758245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2638773$78BFE7BE-376A-4F16-8C32-5C262344FF4F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ab7ae4cff8a8bbbec38509430f55db035cd0f798","datavalue":{"value":"https://doi.org/10.1016/0890-5401(91)90002-j","type":"string"},"datatype":"url"},"type":"statement","id":"Q2638773$530DE92A-C453-4A36-9305-8D26B9E74351","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"46430abf273d358603cca839cd7786fe06261a31","datavalue":{"value":"W2021084256","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2638773$10F520D3-C168-4890-A138-7D213BFBA8F7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90fe594927b3d740b6d58d0f80db3f244713ee72","datavalue":{"value":{"entity-type":"item","numeric-id":3651594,"id":"Q3651594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b36aee3e2d688af881db8443717503dd1563f71","datavalue":{"value":{"amount":"+0.82631594","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":"Q2638773$ECAB6FCF-EF80-41BB-8C25-43F471D73E09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5e227d05c6341b4b1b549415afcedc4fdb76bc2","datavalue":{"value":{"entity-type":"item","numeric-id":3217605,"id":"Q3217605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05858ed5c2d84e43f819aec7e9f9aba22ca4c22b","datavalue":{"value":{"amount":"+0.8238802","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":"Q2638773$AA2150CA-2063-433C-8FC0-AA8D4A5D3FA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11f4cc16378312994f75f82ae31577c18656bbe1","datavalue":{"value":{"entity-type":"item","numeric-id":4636530,"id":"Q4636530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31132623497998456c897be6dd98acb19ad15848","datavalue":{"value":{"amount":"+0.8118009","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":"Q2638773$813C5235-79C0-4345-B9BB-61DD57B82361","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6a86a5b3dbab4e3b585d8531a6afe0b3b02fc11","datavalue":{"value":{"entity-type":"item","numeric-id":4841766,"id":"Q4841766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0b83385b41b04c72b8a6a2a1e59a5339ba92aca","datavalue":{"value":{"amount":"+0.80740625","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":"Q2638773$C1BEB847-4A70-4E3E-8281-E27735820924","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"825997f1222d2762a3875fcda165ed49a1624f9d","datavalue":{"value":{"entity-type":"item","numeric-id":1185002,"id":"Q1185002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96eb927600aff3ad80ab30a0ebb99d8974dd2f74","datavalue":{"value":{"amount":"+0.80576897","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":"Q2638773$07B385F1-7C58-4135-B71A-414B5B893A83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abf11011840de0c5c9e2d74983b232633210a8d7","datavalue":{"value":{"entity-type":"item","numeric-id":3761698,"id":"Q3761698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1c31920b311eaee00e34f1ebb859929ca2844e3","datavalue":{"value":{"amount":"+0.79310995","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":"Q2638773$B34A4127-26F3-43B6-8916-4346D8F8A0B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24b8c676ebd6cc7ac6c852c8d9c4b99d3f128829","datavalue":{"value":{"entity-type":"item","numeric-id":3714069,"id":"Q3714069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"250abdc337924ac9d03d764e13c43e1883f70526","datavalue":{"value":{"amount":"+0.7908445","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":"Q2638773$CDD4B930-857C-4EEA-9C2E-2AF364D657C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9171b16184e0a10ca0b33582fc8269bb07d8310","datavalue":{"value":{"entity-type":"item","numeric-id":4348503,"id":"Q4348503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98d8825131420de7ed2cd2d158a6f8487de53d6e","datavalue":{"value":{"amount":"+0.7893931","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":"Q2638773$CA1A4D06-DAC0-495D-94B7-69AFC65BE519","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f7e44b94780d2487df138fc38317a118e9b5468","datavalue":{"value":{"entity-type":"item","numeric-id":3503093,"id":"Q3503093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e62974360c8fb0876a233a32584038fa138652f","datavalue":{"value":{"amount":"+0.78757405","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":"Q2638773$576FD3B3-66F3-41BE-8387-AE5FE107E4AF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2638773","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2638773"}}}}}