{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T18:58:46Z","timestamp":1774551526540,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1989,12,1]],"date-time":"1989-12-01T00:00:00Z","timestamp":628473600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1989,12]]},"DOI":"10.1007\/bf02125350","type":"journal-article","created":{"date-parts":[[2005,9,14]],"date-time":"2005-09-14T18:43:33Z","timestamp":1126723413000},"page":"385-392","source":"Crossref","is-referenced-by-count":63,"title":["Query complexity, or why is it difficult to separateNP A \u2229coNP A fromP A by random oraclesA?"],"prefix":"10.1007","volume":"9","author":[{"given":"G.","family":"Tardos","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF02125350_CR1","doi-asserted-by":"crossref","unstructured":"A. V.Aho, J. D.Ullman and M.Yannakakis, On Notions of Information Transfer in VLSI Circuits,Proc. 15th STOC,1983, 133\u2013139.","DOI":"10.1145\/800061.808742"},{"key":"BF02125350_CR2","doi-asserted-by":"crossref","unstructured":"L.Babai, Trading group theory for randomness,Proc. 17th STOC (1985), 421\u2013429.","DOI":"10.1145\/22145.22192"},{"key":"BF02125350_CR3","unstructured":"L.Babai, Random oracles separatePSPACE from the polynomial time hierarchy, Technical Report 86-001 (1986), Dept. Comp. Sci., Univ. of Chicago; to appear inInf. Proc. Letters."},{"key":"BF02125350_CR4","doi-asserted-by":"crossref","unstructured":"L.Babai, Arthur-Merlin games: a randomized proof system and a short hierarchy of complexity classes,JCSS, to appear.","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"BF02125350_CR5","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"T. Baker, J. Gill andR. Solovay, Relativizations of theP=?NP question,SIAM J. Comp.,4 (1975), 431\u2013442.","journal-title":"SIAM J. Comp."},{"key":"BF02125350_CR6","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. H. Bennett","year":"1981","unstructured":"C. H. Bennett andJ. Gill, Relative to a random oracleA, P A\u2260NPA\u2260coNPA with probability 1,SIAM J. Comp.,10 (1981), 96\u2013113.","journal-title":"SIAM J. Comp."},{"key":"BF02125350_CR7","doi-asserted-by":"crossref","unstructured":"M.Blum and R.Impagliazzo, Generic oracles and oracle classes,Proc. 28th FOCS (1987), 118\u2013126. Extended Abstract.","DOI":"10.1109\/SFCS.1987.30"},{"key":"BF02125350_CR8","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0304-3975(81)90061-X","volume":"15","author":"R. V. Book","year":"1981","unstructured":"R. V. Book, Bounded query machines: onNP andPSPACE, Theoretical Computer Science,15 (1981), 27\u201339.","journal-title":"Theoretical Computer Science"},{"key":"BF02125350_CR9","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1137\/0213030","volume":"13","author":"R. V. Book","year":"1984","unstructured":"R. V. Book, T. J. Long andA. L. Selman, Quantitative relativization of complexity classes,SIAM J. Comp.,13 (1984), 461\u2013487.","journal-title":"SIAM J. Comp."},{"key":"BF02125350_CR10","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0304-3975(81)90062-1","volume":"15","author":"R. V. Book","year":"1981","unstructured":"R. V. Book andC. Wrathall, Bounded query machines: on NP(and NPQUERY),Theoretical Computer Science,15 (1981), 41\u201350.","journal-title":"Theoretical Computer Science"},{"key":"BF02125350_CR11","doi-asserted-by":"crossref","unstructured":"J. Y.Cai, With Probability One A Random Oracle SeparatesPSPACE from the Polynomial Hierarchy,Proc. 18th STOC (1986), 21\u201329.","DOI":"10.1145\/12130.12133"},{"key":"BF02125350_CR12","doi-asserted-by":"crossref","unstructured":"M. L.Furst, J.Saxe and M.Sipser, Parity, circuits, and the polynomial time hierarchy,Proc. 22nd FOCS (1981), 260\u2013270.","DOI":"10.1109\/SFCS.1981.35"},{"key":"BF02125350_CR13","doi-asserted-by":"crossref","unstructured":"S.Goldwasser, S.Micaly and C.Rackoff, The knowledge complexity of interactive proofsystems,Proc. 17th STOC,1985, 291\u2013304.","DOI":"10.1145\/22145.22178"},{"key":"BF02125350_CR14","doi-asserted-by":"crossref","unstructured":"S.Goldwasser and M.Sipser, Private coins versus public coins in interactive proof systems,Proc. 18th STOC (1986), 59\u201368.","DOI":"10.1145\/12130.12137"},{"key":"BF02125350_CR15","unstructured":"J.Hartmanis and L. A.Hemachandra, One-way functions, robustness, and the non-isomorphism of NP-complete sets,Proc. 2nd Structurde in Complexity Theory, (87), 160\u2013173."},{"key":"BF02125350_CR16","doi-asserted-by":"crossref","unstructured":"S. A.Kurtz, On the Random Oracle Hypothesis,Proc. 14th STOC (1982), 224\u2013230.","DOI":"10.1145\/800070.802195"},{"key":"BF02125350_CR17","doi-asserted-by":"crossref","first-page":"852","DOI":"10.1137\/0216056","volume":"16","author":"S. A. Kurtz","year":"1987","unstructured":"S. A. Kurtz, A Note on Randomized Polynomial Time,SIAM J. Comp.,16 (1987), 852\u2013853.","journal-title":"SIAM J. Comp."},{"key":"BF02125350_CR18","unstructured":"N.Nisan, Probabilistic vc. Deterministic Decision Trees and CREW PRAM Complexity,preprint."},{"key":"BF02125350_CR19","doi-asserted-by":"crossref","unstructured":"V. R.Pratt, Every Prime Has a Succinct Certificate,SIAM J. Comp., (1975), 214\u2013220.","DOI":"10.1137\/0204018"},{"key":"BF02125350_CR20","doi-asserted-by":"crossref","unstructured":"M.Sipser, Borel sets and circuit complexity,Proc. 15th STOC (1983), 61\u201369.","DOI":"10.1145\/800061.808733"},{"key":"BF02125350_CR21","doi-asserted-by":"crossref","unstructured":"A. C.-C.Yao, Separating the polynomial-time hierarchy by oracles,Proc. 26th FOCS (1985), 1\u201310.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02125350.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02125350\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02125350","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T13:07:12Z","timestamp":1586437632000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02125350"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,12]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1989,12]]}},"alternative-id":["BF02125350"],"URL":"https:\/\/doi.org\/10.1007\/bf02125350","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,12]]}}}