{"entities":{"Q649095":{"pageid":650944,"ns":120,"title":"Item:Q649095","lastrevid":51376673,"modified":"2026-01-18T00:04:58Z","type":"item","id":"Q649095","labels":{"en":{"language":"en","value":"Arthur and Merlin as oracles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5982630"}},"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":"Q649095$5164573F-BC0C-44CC-8AF5-347C96CC87E4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c64815712048200a548a35cf724b651f11011b9c","datavalue":{"value":{"text":"Arthur and Merlin as oracles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q649095$EEFD55FF-DB00-4FB4-B73A-3C3384CA1BF4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6a89ca3934607270b028370c18b2129c0d898ff5","datavalue":{"value":"1248.68201","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q649095$E32F3DDD-F3FA-4A36-BE26-CBF643936B28","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"eda281a92a08dab72ad1e081c43daecbcc827585","datavalue":{"value":{"entity-type":"item","numeric-id":649094,"id":"Q649094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$4E7200A0-D433-4D5F-BDE9-C1D6013DD362","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"383a310111755207c53e006053e6b4c2c855846b","datavalue":{"value":{"entity-type":"item","numeric-id":619898,"id":"Q619898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$1E1B4EA2-B5B9-49CD-9B85-996A52B107EA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4472b31ebff52fa964618256e5b76c8eb3e874c2","datavalue":{"value":{"entity-type":"item","numeric-id":172540,"id":"Q172540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$F828B04C-8C14-4FAE-A071-227A5221D865","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1819a172538b9934d4c5de27188f75c7b63afe97","datavalue":{"value":{"time":"+2011-11-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q649095$DA170482-C58A-4A84-A1B4-FDF86B6EF6FE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d0f44765392372b0ee8f253e2781de7e51947bb6","datavalue":{"value":"Problems solvable in deterministic polynomial time given oracle access to the promise version of Arthur-Merlin class are studied. The authors prove that \\(\\mathrm{BPP}_{||}^{\\mathrm{NP}} \\subseteq \\mathrm{P}_{||}^{\\mathrm{prAM}}\\) and \\(\\mathrm{S}_2^p \\subseteq \\mathrm{P}^{\\mathrm{prAM}}\\). In addition, new upper bounds for the classes \\(\\mathrm{S}_2^p\\) and \\(\\mathrm{BPP}_{||}^{\\mathrm{NP}}\\) are provided. These upper bounds have consequences from a derandomization perspective. As corollaries for \\(\\mathrm{BPP}_{||}^{\\mathrm{NP}} \\subseteq \\mathrm{P}_{||}^{\\mathrm{prAM}}\\) is shown that \\(\\mathrm{BPP}_{||}^{\\mathrm{prAM}} = \\mathrm{P}_{||}^{\\mathrm{prAM}}\\) and that \\(\\mathrm{BPP}_{||}^{\\mathrm{NP}} \\subseteq P^{\\Sigma _2 ^p}\\). From \\(S_2^p \\subseteq P^{\\mathrm{prAM}}\\) follows that if NP has polynomial size circuits, then \\(\\mathrm{PH} = \\mathrm{P}^{\\mathrm{prMA}}\\). This fact is weaker than other known results, but has an unexpected proof. Another corollary is that \\(\\mathrm{FP}^{\\mathrm{prMA}} \\subseteq \\mathrm{ZPP}^{\\mathrm{NP}}\\), which is a completely new result. Various results by Cai, Bshouty et al., Fortnow and al. can be proved in alternative ways based on the new results in this paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q649095$F233178F-FE39-4E6F-A303-191572502A67","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"be9b7bf9cd273aeaf91ec2e38cce549e5afc8f07","datavalue":{"value":{"entity-type":"item","numeric-id":192024,"id":"Q192024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$F8A8749E-4F2E-4E1A-B1C1-298B88C81D22","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q649095$31F1A612-7C37-42AC-A52F-BBD829AFA782","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"75e51254228ae4c33a0385330ae8028f4793defc","datavalue":{"value":"5982630","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q649095$4DD82988-3CCC-4F48-9521-69B14D39A5D3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2cb1cb0c79cb1a21eb3a0b0c6ad896ef194c2dc7","datavalue":{"value":"symmetric alternation","type":"string"},"datatype":"string"},"type":"statement","id":"Q649095$0AD34136-B00D-4CE4-9694-B913D3B1AE86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8324689a095d918fc32cc42d5915d2d82a9aa9d4","datavalue":{"value":"Karp-Lipton theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q649095$41BF8B3E-3956-4F7A-AFE7-B4AAE765E3EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c7d2c471197cdfedb43773f3ff2933cb7e4bb2b","datavalue":{"value":"learning circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q649095$BA5582C4-B905-4AE5-9B6B-AD8C0CEC131D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d9399e8a6f1f11c64fa8f4829c5e20aca28693e","datavalue":{"value":"zero-sum games","type":"string"},"datatype":"string"},"type":"statement","id":"Q649095$9F4444B5-D69A-438F-8AC9-A6CBFA3109F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de6ee03cf6adf3a19e6791f59046abe62f938508","datavalue":{"value":"boolean matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q649095$76B920D5-A04B-4F2D-B306-D873FD0FA98E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9098b1420b7e3ea21acc65d55581841a0e219d52","datavalue":{"value":"near-optimal strategies","type":"string"},"datatype":"string"},"type":"statement","id":"Q649095$BB35A00D-B5F4-4847-B7D9-EE316432165C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4a77f4227dd7e22baa9931a8cf71ba3656ccbc51","datavalue":{"value":"conditional derandomization","type":"string"},"datatype":"string"},"type":"statement","id":"Q649095$DC7E49AB-35D9-4333-8B22-72A8B1FBAAEA","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":"Q649095$D48E6F89-8F44-4CC4-AA76-DBA04E862A67","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a923840832fd72033d14853161d5b2c28a549080","datavalue":{"value":"https://doi.org/10.1007/s00037-011-0015-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q649095$7CD76F17-2061-4ED3-BFB2-A76B54589C40","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f6a8e6ee8c6063ae5e192827f4ea0eaca1605b50","datavalue":{"value":"W2028556586","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q649095$BF8AA9DA-28BF-440C-BA27-777E6C82AEAE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ada50eb084717f8ed92ebbcdcaef4dbeac54cb8","datavalue":{"value":{"entity-type":"item","numeric-id":1322876,"id":"Q1322876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$7C807CFF-1ED5-4532-949C-E4B5C21C6090","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4950dd5bc273443524aee7cc7cc2b265a1ecbcdf","datavalue":{"value":{"entity-type":"item","numeric-id":5941070,"id":"Q5941070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$4B2113F6-15C6-4BE3-B0C2-B2A6C7C3EA5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f2629667958791e2ac9814559cfab94e339d880","datavalue":{"value":{"entity-type":"item","numeric-id":674343,"id":"Q674343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$ECCD2E41-2E38-4EDE-8DC7-25C41CEBA6FB","rank":"normal"},{"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":"Q649095$71098B57-57AF-419A-A54E-A87C98E4CE7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb8485af4f2dd4cfae0164b58f96a808b5d82c01","datavalue":{"value":{"entity-type":"item","numeric-id":1924380,"id":"Q1924380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$E0FE10FB-6AD4-4C27-B972-128EBE2CF466","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b41077c97b504be2e6ac56fb7b26543ed4cb1d08","datavalue":{"value":{"entity-type":"item","numeric-id":859979,"id":"Q859979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$A6CD235B-6272-4C63-9BFE-18A4952C857F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"668c5b2da34a3aec680c0f5e66f9e4d87ccb409e","datavalue":{"value":{"entity-type":"item","numeric-id":1351599,"id":"Q1351599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$5B6169F0-F5BC-4702-B23B-F3EFDF8C73B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04a378fa25ecf4466a1bfafa00fa7670224905dd","datavalue":{"value":{"entity-type":"item","numeric-id":5449801,"id":"Q5449801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$4ED94B27-2E74-49FB-A666-D0EBD759EFB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89b4e4ff27e78e006949894738cc76e547d78fbf","datavalue":{"value":{"entity-type":"item","numeric-id":3599130,"id":"Q3599130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$91E6A008-9061-498D-AC0F-E645913D7EE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab45965f2c1409e1b2d48454d9f1227cdf90770f","datavalue":{"value":{"entity-type":"item","numeric-id":1024660,"id":"Q1024660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$B863105B-B1F3-4B4F-80A0-AD3A8C901E78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67d99088bfc45b19e7ae51880c26b5822e0a331a","datavalue":{"value":{"entity-type":"item","numeric-id":2475408,"id":"Q2475408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$06EC4B1F-BDDA-4EA7-8175-C2C6DF85E27E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc79bbac2f848100a966a182e11ca63cddd39c35","datavalue":{"value":{"entity-type":"item","numeric-id":4526985,"id":"Q4526985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$C64D9DB7-6CF7-49F7-B310-7D769011A959","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fb1d4a4467e7a66ae16006a64871f949eba352e","datavalue":{"value":{"entity-type":"item","numeric-id":3149879,"id":"Q3149879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$96239694-678A-4056-ABD5-45A9C855A45E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2120b12ab96678ee03b84909ec3e390673400419","datavalue":{"value":{"entity-type":"item","numeric-id":4210150,"id":"Q4210150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$2729FDB3-782A-42AE-BE3E-B8E5DD4DC46E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2df7e33e1d2f33d6300925582588504377a9a859","datavalue":{"value":{"entity-type":"item","numeric-id":2817668,"id":"Q2817668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$2CF9426D-DCA1-48E1-ADF6-E49BEB88D034","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d342ae16c68bc818f23832166ad4b70cc0dba85","datavalue":{"value":{"entity-type":"item","numeric-id":813315,"id":"Q813315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$C9F4EEEA-9661-4657-BAE2-0A6E769CC09A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a77c342c1e43c98b625488907d9962b1f6ffb9b","datavalue":{"value":{"entity-type":"item","numeric-id":1182120,"id":"Q1182120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$5C67D81E-8394-42B2-B483-3DE7E7A7E49C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b409306bdf364930adcbf624496cede43048b2af","datavalue":{"value":{"entity-type":"item","numeric-id":1337458,"id":"Q1337458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$FBB1331A-D395-46A3-8D64-FA9299B8E506","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1644b84d3838bf2933f19816a06e0772adad2efa","datavalue":{"value":{"entity-type":"item","numeric-id":1272661,"id":"Q1272661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$8B25D76A-1879-49AD-B56F-3A326827F650","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25f3f5fea7034f6c7f89c99e89c8c1b3902bd45c","datavalue":{"value":{"entity-type":"item","numeric-id":2460030,"id":"Q2460030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649095$7DEDE503-CCD4-4D6F-A3EC-C905959FFAC8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"928cedbcc9d4862dd718a64f0c0ec55040d4f648","datavalue":{"value":"10.1007/S00037-011-0015-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q649095$51E2A359-9871-459A-A830-957B49A15821","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4556af22cfa2c62150352ab141193691690e74fb","datavalue":{"value":{"entity-type":"item","numeric-id":3599130,"id":"Q3599130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80404dcfedc023f18812934e347e92664ce72dfe","datavalue":{"value":{"amount":"+0.9635103344917296","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":"Q649095$95FE30A7-AD8A-4173-B195-C4B9E889175C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4617599a984945a3b99480b07e85e8ca75627ef3","datavalue":{"value":{"entity-type":"item","numeric-id":4910716,"id":"Q4910716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0a777794ca1b1c5e566d4f8772de2fdb78c5310","datavalue":{"value":{"amount":"+0.8219689726829529","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":"Q649095$8F3793AC-53A4-4FC8-B1B4-16FD465220AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8326fa50fdbdc26a99c1bea1490a855b44143e9","datavalue":{"value":{"entity-type":"item","numeric-id":645124,"id":"Q645124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b9714c07ab63e44d7d9f1699d8c06d3735faf5d","datavalue":{"value":{"amount":"+0.8090256452560425","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":"Q649095$856832BA-C86A-40E9-834A-8339E01F5D05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca15eb8662b0748e09b81fb52482afed38dea4df","datavalue":{"value":{"entity-type":"item","numeric-id":2012178,"id":"Q2012178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e33b0011f64f4444893feac216f45f8a2b257692","datavalue":{"value":{"amount":"+0.80107182264328","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":"Q649095$CD3F00C4-2DC2-4722-8918-1338D741110E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c920e7b191a07de1ff82fb439b4803631188054","datavalue":{"value":{"entity-type":"item","numeric-id":1601037,"id":"Q1601037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e2811aefc4bfbefdf3156f636802a0762a054ca","datavalue":{"value":{"amount":"+0.7910894751548767","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":"Q649095$A30C21DC-10F9-4D30-9BC2-F93565A784DF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:649095","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:649095"}}}}}