{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T02:48:45Z","timestamp":1778294925015,"version":"3.51.4"},"reference-count":36,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1992,1,1]],"date-time":"1992-01-01T00:00:00Z","timestamp":694224000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1992,1,1]],"date-time":"1992-01-01T00:00:00Z","timestamp":694224000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2004,3,25]],"date-time":"2004-03-25T00:00:00Z","timestamp":1080172800000},"content-version":"vor","delay-in-days":4467,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1992,1]]},"DOI":"10.1016\/0304-3975(92)90318-a","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T23:47:37Z","timestamp":1027640857000},"page":"309-318","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":8,"title":["Separating complexity classes with tally oracles"],"prefix":"10.1016","volume":"92","author":[{"given":"Lane A.","family":"Hemachandra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roy S.","family":"Rubinstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(92)90318-A_BIB1","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","article-title":"Relativizations of the P=?NP question","volume":"4","author":"Baker","year":"1975","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(92)90318-A_BIB2","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1007\/BF00264313","article-title":"Sets with small generalized Kolmogorov complexity","volume":"23","author":"Balc\u00e1zar","year":"1986","journal-title":"Acta Inform."},{"key":"10.1016\/0304-3975(92)90318-A_BIB3","first-page":"308","article-title":"Sparse oracles and uniform complexity classes","author":"Balc\u00e1zar","year":"1984","journal-title":"Proc. 25th IEEE Symp. Foundations of Computer Science"},{"key":"10.1016\/0304-3975(92)90318-A_BIB4","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1145\/5925.5937","article-title":"The polynomial-time hierarchy and sparse oracles","volume":"33","author":"Balc\u00e1zar","year":"1986","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(92)90318-A_BIB5","series-title":"EATCS Monographs in Theoretical Computer Science","article-title":"Structural Complexity II","author":"Balc\u00e1zar","year":"1990"},{"key":"10.1016\/0304-3975(92)90318-A_BIB6","doi-asserted-by":"crossref","DOI":"10.1109\/SFCS.1987.30","article-title":"Generic oracles and oracle classes","author":"Blum","year":"1987","journal-title":"Proc. 28th IEEE Symp. Foundations of Computer Science"},{"key":"10.1016\/0304-3975(92)90318-A_BIB7","series-title":"Proc. 4th Ann. Symp. Theoretical Aspects of Computer Science","first-page":"1","article-title":"Towards a theory of relativizations: Positive relativizations","volume":"247","author":"Book","year":"1987"},{"key":"10.1016\/0304-3975(92)90318-A_BIB8","series-title":"Tech. Report CS-018\u29f891","article-title":"Complexity classes and sparse oracles","author":"Bovet","year":"1991"},{"key":"10.1016\/0304-3975(92)90318-A_BIB9","series-title":"Tech. Report CS-017\u29f891","article-title":"A uniform approach to define complexity classes","author":"Bovet","year":"1991"},{"key":"10.1016\/0304-3975(92)90318-A_BIB10","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1137\/0218007","article-title":"The boolean hiearchy II: Applications","volume":"18","author":"Cai","year":"1989","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(92)90318-A_BIB11","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0019-9958(84)80056-X","article-title":"The complexity of promise problems with applications to public-key cryptography","volume":"61","author":"Even","year":"1984","journal-title":"Inform. and Control"},{"key":"10.1016\/0304-3975(92)90318-A_BIB12","series-title":"Proc. 21st ACM Symp. Theory of Computing","first-page":"148","article-title":"Probabilistic computation and linear time","author":"Fortnow","year":"1989"},{"key":"10.1016\/0304-3975(92)90318-A_BIB13","series-title":"Proc. 13th Symp. Mathematical Foundations of Computer Science","first-page":"300","article-title":"Strong and robustly strong polynomial time reducibilities to sparse sets","volume":"Vol. 324","author":"Gavald\u00e0","year":"1988"},{"key":"10.1016\/0304-3975(92)90318-A_BIB14","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","article-title":"Computational complexity of probabilistic Turing machines","volume":"6","author":"Gill","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(92)90318-A_BIB15","series-title":"Proc. 24th IEEE Symp. Foundations of Computer Science","first-page":"210","article-title":"Algebras of feasible functions","author":"Gurevich","year":"1983"},{"key":"10.1016\/0304-3975(92)90318-A_BIB16","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0304-3975(91)90323-T","article-title":"One-way functions and the non-isomorphism of NP-complete sets","volume":"81","author":"Hartmanis","year":"1991","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(92)90318-A_BIB17","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0304-3975(88)90022-9","article-title":"Complexity classes without machines: On complete languages for UP","volume":"58","author":"Hartmanis","year":"1988","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(92)90318-A_BIB18","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0020-0190(88)90176-7","article-title":"On sparse oracles separating feasible complexity classes","volume":"28","author":"Hartmanis","year":"1988","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(92)90318-A_BIB19","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0304-3975(90)90138-8","article-title":"Robust machines accept easy sets","volume":"74","author":"Hartmanis","year":"1990","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(92)90318-A_BIB20","series-title":"Proc. 12th Internet. Collo. Automata, Languages, and Programming","first-page":"250","article-title":"On complete problems for NP\u2229coNP","volume":"Vol. 194","author":"Hartmanis","year":"1985"},{"key":"10.1016\/0304-3975(92)90318-A_BIB21","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/S0019-9958(86)80012-2","article-title":"On relativized exponential and probabilistic complexity classes","volume":"71","author":"Heller","year":"1986","journal-title":"Inform. and Control"},{"key":"10.1016\/0304-3975(92)90318-A_BIB22","article-title":"On relativization and the existence of Turing complete sets","volume":"14627","author":"Hemachandra","year":"1989"},{"key":"10.1016\/0304-3975(92)90318-A_BIB23","series-title":"Proc. 9th Conf. Foundations of Software Technology and Theoretical Computer Science","first-page":"193","article-title":"On the limitations of locally robust positive reductions","volume":"Vol. 405","author":"Hemachandra","year":"1989"},{"key":"10.1016\/0304-3975(92)90318-A_BIB24","series-title":"Proc. 4th Structure in Complexity Theory Conference","first-page":"3","article-title":"Oracles for structural properties: the isomorphism problem and public-key cryptography","author":"Homer","year":"1989"},{"key":"10.1016\/0304-3975(92)90318-A_BIB25","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0304-3975(89)90164-3","article-title":"Relativizing relativized computations","volume":"68","author":"Immerman","year":"1989","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(92)90318-A_BIB26","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1016\/0022-0000(89)90024-X","article-title":"PNP[log n]and sparse Turing-complete sets for NP","volume":"39","author":"Kadin","year":"1989","journal-title":"J. Comput. Systems Sci."},{"key":"10.1016\/0304-3975(92)90318-A_BIB27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(82)90085-8","article-title":"Strong nondeterministic polynomial-time reducibilities","volume":"21","author":"Long","year":"1982","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(92)90318-A_BIB28","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1145\/5925.5938","article-title":"Relativizing complexity classes with sparse oracles","volume":"33","author":"Long","year":"1986","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(92)90318-A_BIB29","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/322290.322306","article-title":"Relativized questions involving probabilistic algorithms","volume":"29","author":"Rackoff","year":"1982","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(92)90318-A_BIB30","author":"Regan","year":"1989","journal-title":"Provable complexity properties and constructive reasoning"},{"key":"10.1016\/0304-3975(92)90318-A_BIB31","series-title":"Ph.D Thesis","article-title":"Structural Complexity Classes of Sparse Sets: Intractability, Data Compression and Printability","author":"Rubinstein","year":"1988"},{"key":"10.1016\/0304-3975(92)90318-A_BIB32","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0890-5401(88)90030-2","article-title":"Promise problems complete for complexity classes","volume":"78","author":"Selman","year":"1988","journal-title":"Inform. and Comput."},{"key":"10.1016\/0304-3975(92)90318-A_BIB33","series-title":"Proc. 9th Internat. Collo. Automata, Languages, and Programming","article-title":"On relativization and the existence of complete sets","volume":"Vol. 140","author":"sipser","year":"1982"},{"key":"10.1016\/0304-3975(92)90318-A_BIB34","doi-asserted-by":"crossref","DOI":"10.1007\/BF02125350","article-title":"Query complexity, or why is it difficult to separate NPA\u2229coNPA from PA by random oracles A","volume":"9","author":"Tardos","year":"1989","journal-title":"Combinatorica"},{"key":"10.1016\/0304-3975(92)90318-A_BIB35","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","article-title":"The relative complexity of checking and evaluating","volume":"5","author":"Valiant","year":"1976","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(92)90318-A_BIB36","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0022-0000(85)90040-6","article-title":"Relativized circuit complexity","volume":"31","author":"Wilson","year":"1985","journal-title":"J. Comput. System Sci."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759290318A?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759290318A?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T04:18:09Z","timestamp":1757477889000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/030439759290318A"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,1]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,1]]}},"alternative-id":["030439759290318A"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(92)90318-a","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1992,1]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Separating complexity classes with tally oracles","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/0304-3975(92)90318-A","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 1992 Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}