{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T03:18:25Z","timestamp":1778296705228,"version":"3.51.4"},"reference-count":28,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1992,10,1]],"date-time":"1992-10-01T00:00:00Z","timestamp":717897600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":7594,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1992,10]]},"DOI":"10.1016\/0304-3975(92)90125-y","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T23:47:37Z","timestamp":1027640857000},"page":"263-283","source":"Crossref","is-referenced-by-count":84,"title":["A uniform approach to define complexity classes"],"prefix":"10.1016","volume":"104","author":[{"given":"Daniel P.","family":"Bovet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierluigi","family":"Crescenzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Riccardo","family":"Silvestri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(92)90125-Y_BIB1","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0304-3975(80)90027-4","article-title":"On counting problems and the polynomial-time hierarchy","volume":"12","author":"Angluin","year":"1980","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(92)90125-Y_BIB2","first-page":"421","article-title":"Trading group theory for randomness","author":"Babai","year":"1985","journal-title":"Proc. 17th ACM Symp. Theory of Comput."},{"key":"10.1016\/0304-3975(92)90125-Y_BIB3","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)90125-Y_BIB4","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0304-3975(79)90043-4","article-title":"A second step toward the polynomial hierarchy","volume":"8","author":"Baker","year":"1979","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(92)90125-Y_BIB5","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1137\/0214012","article-title":"Simplicity, relativizations and nondeterminism","volume":"14","author":"Balc\u00e1zar","year":"1985","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(92)90125-Y_BIB6","volume":"Vol. 1","author":"Balc\u00e1zar","year":"1988"},{"key":"10.1016\/0304-3975(92)90125-Y_BIB7","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1051\/ita\/1988220202271","article-title":"Immunity and simplicity in relativizations of probabilistic complexity classes","volume":"22","author":"Balc\u00e1zar","year":"1988","journal-title":"RAIRO Theoretical Informatics and Applications"},{"key":"10.1016\/0304-3975(92)90125-Y_BIB8","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","article-title":"Relative to a random oracle A, PA \u2260 NPA \u2260 co-NPA with probability 1","volume":"10","author":"Bennett","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(92)90125-Y_BIB9","article-title":"Complexity Classes and Sparse Oracles","author":"Bovet","year":"1991","journal-title":"Proc. 6th Structure in Complexity Theory Conference"},{"key":"10.1016\/0304-3975(92)90125-Y_BIB10","doi-asserted-by":"crossref","first-page":"1232","DOI":"10.1137\/0217078","article-title":"The boolean hierarchy I: structural properties","volume":"17","author":"Cai","year":"1988","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(92)90125-Y_BIB11","first-page":"229","article-title":"On the power of parity polynomial time","volume":"Vol. 349","author":"Cai","year":"1989"},{"key":"10.1016\/0304-3975(92)90125-Y_BIB12","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","article-title":"Alternation","volume":"28","author":"Chandra","year":"1981","journal-title":"J. Assoc. Comput. Math."},{"key":"10.1016\/0304-3975(92)90125-Y_BIB13","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)90125-Y_BIB14","first-page":"59","article-title":"Structure of complexity classes: separations, collapses, and completeness","volume":"Vol. 324","author":"Hemachandra","year":"1988"},{"key":"10.1016\/0304-3975(92)90125-Y_BIB15","first-page":"159","article-title":"Probabilistic machines, oracles and quantifiers","volume":"Vol. 1141","author":"Hinman","year":"1984"},{"key":"10.1016\/0304-3975(92)90125-Y_BIB16","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1109\/SCT.1988.5260","article-title":"Decision tree and downward closures","author":"Impagliazzo","year":"1988","journal-title":"Proc. 3rd Structure in Complexity Theory Conference"},{"key":"10.1016\/0304-3975(92)90125-Y_BIB17","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1051\/ita\/1990240302291","article-title":"A note on separating the relativized polynomial-time hierarchy by immune sets","volume":"24","author":"Ko","year":"1990","journal-title":"RAIRO Theoretical Informatics and Applications"},{"key":"10.1016\/0304-3975(92)90125-Y_BIB18","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","article-title":"On the structure of polynomial-time reducibilities","volume":"22","author":"Ladner","year":"1975","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0304-3975(92)90125-Y_BIB19","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/0890-5401(89)90022-9","article-title":"Relativized Arthur-Merlin versus Merlin-Arthur games","volume":"80","author":"Santha","year":"1989","journal-title":"Inform. and Comput."},{"key":"10.1016\/0304-3975(92)90125-Y_BIB20","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(82)90114-1","article-title":"A uniform approach to obtain diagonal sets in complexity classes","volume":"18","author":"Sch\u00f6ning","year":"1982","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(92)90125-Y_BIB21","volume":"Vol. 211","author":"Sch\u00f6ning","year":"1985"},{"key":"10.1016\/0304-3975(92)90125-Y_BIB22","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0213023","article-title":"Immunity, relativizations, and nondeterminism","volume":"13","author":"Sch\u00f6ning","year":"1984","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(92)90125-Y_BIB23","first-page":"523","article-title":"On relativization and the existence of complete sets","volume":"Vol. 140","author":"Sipser","year":"1982"},{"key":"10.1016\/0304-3975(92)90125-Y_BIB24","first-page":"733","article-title":"A combinatorial technique for separating counting complexity classes","volume":"Vol. 372","author":"Tor\u00e1n","year":"1989"},{"key":"10.1016\/0304-3975(92)90125-Y_BIB25","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1007\/3-540-16486-3_109","article-title":"Diagonalization methods in a polynomial setting","author":"Torenvliet","year":"1986","journal-title":"Proc. 1st Structure in Complexity Theory Conference"},{"key":"10.1016\/0304-3975(92)90125-Y_BIB26","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00289117","article-title":"The complexity of combinatorial problems with succint input representation","volume":"23","author":"Wagner","year":"1986","journal-title":"Acta Inform."},{"key":"10.1016\/0304-3975(92)90125-Y_BIB27","first-page":"485","article-title":"On the Boolean Closure of NP","volume":"Vol. 199","author":"Wechsung","year":"1985"},{"key":"10.1016\/0304-3975(92)90125-Y_BIB28","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1016\/0022-0000(88)90037-2","article-title":"Probabilistic quantifiers and games","volume":"36","author":"Zachos","year":"1988","journal-title":"J. Comput. System Sci."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759290125Y?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759290125Y?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,13]],"date-time":"2019-04-13T00:20:35Z","timestamp":1555114835000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/030439759290125Y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,10]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,10]]}},"alternative-id":["030439759290125Y"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(92)90125-y","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1992,10]]}}}