{"entities":{"Q1069299":{"pageid":1080051,"ns":120,"title":"Item:Q1069299","lastrevid":48890638,"modified":"2026-01-06T02:32:15Z","type":"item","id":"Q1069299","labels":{"en":{"language":"en","value":"Relativized circuit complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3934408"}},"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":"Q1069299$0875A00A-CD16-40BF-B514-FAB60E95F197","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"73a3c41065c0627389fac808fe5f82fe43e71d91","datavalue":{"value":{"text":"Relativized circuit complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1069299$32AFFB8A-1519-445C-9AFC-82E0BEC70788","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4bbe14cacb6de58f0db96a07ef37bb0f52a868ab","datavalue":{"value":"0583.68023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069299$59FDFA1C-FEA3-4838-9690-EEB5D42A6CE9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"496ebf2413fe17e7b9908c7c6eedd7c594e86c47","datavalue":{"value":"10.1016/0022-0000(85)90040-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069299$7669706E-7109-4A63-843E-3CF6F456C049","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5f2804a1407a7965ebc145bb6ecab9495d43c906","datavalue":{"value":{"entity-type":"item","numeric-id":1069298,"id":"Q1069298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069299$AC057E72-BF51-4E23-A663-60FED664543C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069299$9C2885F8-19ED-4525-B7F5-3EB4E9B42A31","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1069299$B7735839-B235-4A34-848C-A9F34DEFAA23","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"97ab8d5e479aee3d6a87d764e68e17f350fd5357","datavalue":{"value":"We compare the measures of sequential time modelled using Turing machines and of parallel size modelled using Boolean circuits. This is done by constructing oracles which show certain relationships between complexity classes. An oracle \\(B\\) is shown for which \\(\\Delta_ 2^{P,B}\\) has \\(2n+o(n)\\) size circuits relative to B. On the other hand, we give a C so that \\(P^ C\\) does not, for any k, have size \\(n^ k\\) circuits relative to C and yet \\(NP^ C\\neq coNP^ C\\). These techniques can be combined to yield a D relative to which \\(P^ D\\) has \\(2n+o(n)\\) size circuits but \\(R^ D\\) does not have size \\(n^ k\\) circuits for any k.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069299$C0A0BAD1-96B1-46D6-82F6-A1665290EDC6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069299$DB69E395-3A72-475D-B99C-F55196349091","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069299$716B6089-BE21-48E5-8FAD-E681C2ADC4C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069299$516CFEDE-68FB-4219-8F75-A2090779826B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7d2abba7c7b56400972ea66ff7cf866a695b0139","datavalue":{"value":"3934408","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069299$665CF4EC-78DE-4968-94E4-4C902EEA776D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77fab9addd78862b9ba4fca8c004ad8dab47a66a","datavalue":{"value":"sequential time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069299$62D92A74-45F0-4BAD-81F3-6CF0A15869C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b2518fecb1c0b57735793eae5817ca06057a14d","datavalue":{"value":"Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069299$A88AA445-EF0E-4378-88FB-5C61481C2FAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9e88caeadec7ebb0b72f1f0fc1b4d0f8d06893a","datavalue":{"value":"parallel size","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069299$E543C55E-7F7F-4B60-A4D5-2693B85E8853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d463b247e815798d799459507ebd3bcfc87bfad","datavalue":{"value":"Boolean circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069299$20286263-9BE5-4B27-995E-CECA8EE177A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c912dd45456959aa9594fa8a89e3f787ad398ae","datavalue":{"value":"oracles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069299$296E7175-F99B-497D-8CA7-715BC645B9F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069299$4D1EE604-044E-4053-BD3A-482156262092","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":"Q1069299$0AFCFA8C-07AD-4EB9-90C8-384C3B97A896","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9e8878d95e7a7914dd1e850c90335ab6b14a7a77","datavalue":{"value":"https://doi.org/10.1016/0022-0000(85)90040-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1069299$20D21FAE-F01B-4BF0-AC18-A9F42CBF9659","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0151a3275e1733360b2cc24a33edd498cafb356f","datavalue":{"value":"W1988127406","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069299$5FBF552D-2553-45FB-9BCE-D45051E94E8F","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":"Q1069299$14146ED5-C75F-45AE-A4CC-F2144E6D050B","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":"Q1069299$34C9089A-982D-4DF2-BAAD-633ED24F1030","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58af9a438ca79f17e01d4568050919b82873e432","datavalue":{"value":{"entity-type":"item","numeric-id":794625,"id":"Q794625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069299$107E3640-B032-4808-8059-A76EEB1720DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb24dff4005148539085ff5c885035cfccaed69","datavalue":{"value":{"entity-type":"item","numeric-id":4140967,"id":"Q4140967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069299$D7FE94E5-9240-4E29-8234-8ACC20D2DA00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca35de5f0bc76f3c53e6ff2d28052786022d5dae","datavalue":{"value":{"entity-type":"item","numeric-id":3663271,"id":"Q3663271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069299$D4684B55-5C3D-4852-BA23-190E326A02B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab289263ac80a8df854a0b026020c7e068e5240d","datavalue":{"value":{"entity-type":"item","numeric-id":1052094,"id":"Q1052094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069299$5543DCCE-5DF2-4ECB-9A56-BA5A5937E86D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e266c332c8c722703a0d32ad33eb1d65fa4f734","datavalue":{"value":{"entity-type":"item","numeric-id":4131019,"id":"Q4131019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069299$3ECBA838-E26B-4509-B805-CF485BDD43DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ade66df427687f4ec50eb2cfe400c9165af764e9","datavalue":{"value":{"entity-type":"item","numeric-id":3935473,"id":"Q3935473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069299$85584B68-4C9E-43A8-9753-7449B9B5B2A1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1a28f9b9129bfe5a1286ea347849d2b26e929f9","datavalue":{"value":{"entity-type":"item","numeric-id":1208410,"id":"Q1208410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b5fc93332f54ed3c6810f6bdb729676e56474a4","datavalue":{"value":{"amount":"+0.8498082756996155","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":"Q1069299$310695DD-3D24-4B24-AFAA-389F655A11A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48b25c73b602aeed12f85945e918e90caf0ca40d","datavalue":{"value":{"entity-type":"item","numeric-id":3763591,"id":"Q3763591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d356a9f791291388e8af3d2d44438e468ec806d","datavalue":{"value":{"amount":"+0.8452578186988831","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":"Q1069299$F21C6696-738E-4D58-AB4E-696993DB73A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b63c817b09e5bf5c79589acd3af335c22e762cd","datavalue":{"value":{"entity-type":"item","numeric-id":4723303,"id":"Q4723303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c2e9e25d63ec47e400e4cd8597e779f763cc405","datavalue":{"value":{"amount":"+0.8447182774543762","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":"Q1069299$C1078D57-76CC-4949-A802-5CD39A3B5F7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"443da56195c385d4cc0144a094c496f296f3735d","datavalue":{"value":{"entity-type":"item","numeric-id":1822968,"id":"Q1822968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abe29ff58b43e836d3994fcf8a4646fe228bdc53","datavalue":{"value":{"amount":"+0.8331562280654907","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":"Q1069299$221A7B6F-73E1-4EEC-A0F4-82125E70959B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d9031b73ffb0f4c256e887d2438ff51cf9e7d9d","datavalue":{"value":{"entity-type":"item","numeric-id":3761699,"id":"Q3761699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cff14a0297afc94c4ccc9e9dfeb7f98f59f59ad3","datavalue":{"value":{"amount":"+0.8263959884643555","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":"Q1069299$D68F4D4A-60A4-49E8-AFE4-7F2F55B7BC35","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1069299","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1069299"}}}}}