{"entities":{"Q912625":{"pageid":914473,"ns":120,"title":"Item:Q912625","lastrevid":49374934,"modified":"2026-01-07T01:32:22Z","type":"item","id":"Q912625","labels":{"en":{"language":"en","value":"Query complexity, or why is it difficult to separate \\(NP^ A\\cap coNP^ A\\) from \\(P^ A\\) by random oracles A?"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4145338"}},"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":"Q912625$29BCAF55-29A9-4CA7-87BF-E13F97D88029","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d09e33362e98566f0502264762c4a7a2ee49a7a6","datavalue":{"value":{"text":"Query complexity, or why is it difficult to separate \\(NP^ A\\cap coNP^ A\\) from \\(P^ A\\) by random oracles A?","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q912625$A48A4259-4110-4929-A4D5-E95ECFBB498C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4d3ae7aba54de63a3086c73de1e16838b2469bf5","datavalue":{"value":"0698.68051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912625$AAFA7C42-D403-4AAB-A3E2-8104CE6D8FD5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0921c0bf9faa5ed2507eb5821777a89a32fbbb07","datavalue":{"value":"10.1007/BF02125350","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912625$054BD03E-932A-4B00-A3FB-93238D08F164","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q912625$F71DE0CB-B08D-4190-82C5-5A206F209294","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":"Q912625$09069245-DC71-46A7-B5FB-C76CA1745804","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912625$A7D8045A-21C0-4FFB-B400-97ED6C776EFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912625$A299735A-2599-4A50-A8E8-E6AF4312B4D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912625$A967010F-CB5A-4914-89D8-54508703A48B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1c4d218d422fe083a67dff80f856160539c1c3bd","datavalue":{"value":"4145338","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912625$2F38BF2A-3AAC-452A-AD54-C934E4E49321","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c38b82089edea4c799aa2fc794a7bae2918610bf","datavalue":{"value":"query-time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q912625$4EC6D3F3-C53B-46C6-A917-F4962E57E5D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dfcfd71c905d64e84c230c37388dfa7466b2a4e5","datavalue":{"value":"oracle queries","type":"string"},"datatype":"string"},"type":"statement","id":"Q912625$BDE8B556-17DB-4FAE-B94B-DADDF0AFE802","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ae6fa0aa641b7c9c64ea87ff6839155fe57995f","datavalue":{"value":"query-space complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q912625$911B89D3-9ED1-455B-AA13-6107D2D3FB53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b2518fecb1c0b57735793eae5817ca06057a14d","datavalue":{"value":"Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q912625$78D64A2A-CA82-4FCA-8228-628467AC3662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b80c99afc4950f85b79a2fe3707eb2e870b9567f","datavalue":{"value":"separation","type":"string"},"datatype":"string"},"type":"statement","id":"Q912625$5DB69DAA-A56A-474F-B613-EE1C927F2E0A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bfb4a17abdcf37f7572da8c995af52b66fc8d692","datavalue":{"value":{"entity-type":"item","numeric-id":168595,"id":"Q168595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q912625$45F4090F-6FD5-4576-96CF-16B3C2926120","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":"Q912625$794882E1-67DD-4D11-A5C5-B3AB40CBF47B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b9c0297ccc7943530d7e60dae41b7cff33d7166","datavalue":{"value":{"entity-type":"item","numeric-id":1106840,"id":"Q1106840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q912625$168CD669-5B9F-4DAB-AEDF-40BD1C12422A","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":"Q912625$788F0614-33BC-4755-B54C-B6B28C8AFE54","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":"Q912625$98CEFE8C-376C-4E77-B531-67370017228F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf08e672e6567347cc84e2210bda4ae13680dff5","datavalue":{"value":{"entity-type":"item","numeric-id":1158751,"id":"Q1158751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q912625$E04D5FBE-956D-419F-A810-7A0F4BA8A2DA","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":"Q912625$A6CDBA5F-0E9D-4394-9575-A88FE54C9677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d6a6c22a928fa8dd018c35c3d3a9912036e4770","datavalue":{"value":{"entity-type":"item","numeric-id":1158752,"id":"Q1158752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q912625$594B4601-9A7C-4356-BE0C-E4F306E6A8DA","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":"Q912625$8C0C14D3-1B90-4465-9BFC-6511FF54BE63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b4feb58a2ab8f89621eb4513d36fed4a40d625b","datavalue":{"value":{"entity-type":"item","numeric-id":4365519,"id":"Q4365519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q912625$06E0D2F9-7F7A-4B7B-86A2-FE9A466CE77B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6364e30db5bf5ba9c696668d94376167a6d7e110","datavalue":{"value":{"entity-type":"item","numeric-id":3773343,"id":"Q3773343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q912625$3BFF7495-6E38-4ED6-B58D-01878698B170","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b3ef38ef005c69e7bd0fea842b7da511c1842a8","datavalue":{"value":{"entity-type":"item","numeric-id":4077450,"id":"Q4077450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q912625$79481880-D9EC-43BE-A714-DC650F569762","rank":"normal"}],"P1643":[{"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":"47c7f7baa127696b9ff72e77de5c1f45218f1ebf","datavalue":{"value":{"amount":"+0.8379834890365601","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":"Q912625$2B720F6B-42A8-4DB0-A668-2747868D6A62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"878898f222338e38d5ed6038974e48ad176da3d7","datavalue":{"value":{"entity-type":"item","numeric-id":3343440,"id":"Q3343440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"baaad9cd033516a28390fdfdcb9f4283e1887ba4","datavalue":{"value":{"amount":"+0.8280305862426758","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":"Q912625$DF335101-BAF7-41DE-A4CE-128F3836A8FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c134d1afabca82fcc71c76c536adc5e32dedcf7","datavalue":{"value":{"entity-type":"item","numeric-id":3734382,"id":"Q3734382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c5fb3cea55ba3c331bd2ca19e2b29d5edc37feb","datavalue":{"value":{"amount":"+0.8240411281585693","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":"Q912625$0E10FDC2-59C1-4BC4-9384-D8F87DF15E76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f437c328148ad24c2d3765ee0b8797f0262f0575","datavalue":{"value":{"entity-type":"item","numeric-id":4721649,"id":"Q4721649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6be0c21e90fc0cde636e86f0cb4cf52456314a4c","datavalue":{"value":{"amount":"+0.8088423609733582","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":"Q912625$F193DC95-9710-4C0B-906D-EDB06A53D00A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6fbf1b0488a013b37e2e9e9666f8dd54f14e231c","datavalue":{"value":{"entity-type":"item","numeric-id":3779739,"id":"Q3779739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b627e118006e4a5e19eed368c4c761bac5787782","datavalue":{"value":{"amount":"+0.7962533235549927","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":"Q912625$F9FEE7EA-3277-4664-B70B-A093EE1FC7D5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:912625","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:912625"}}}}}