{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T23:27:53Z","timestamp":1673306873112},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1991,7]]},"DOI":"10.1145\/116825.116858","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"752-773","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":75,"title":["Complexity classes defined by counting quantifiers"],"prefix":"10.1145","volume":"38","author":[{"given":"Jacobo","family":"Tor\u00e1n","sequence":"first","affiliation":[{"name":"Univ. Politecnica de Catalun\u02dca, Barcelona, Spain"}]}],"member":"320","published-online":{"date-parts":[[1991,7]]},"reference":[{"key":"e_1_2_1_1_2","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 D","year":"1980","unstructured":"ANGLUIN , D . On counting problems and the polynomial-time hierarchy . Theoret. Comput. Sci. 12 ( 1980 ), 161 - 173 . ANGLUIN, D. On counting problems and the polynomial-time hierarchy. Theoret. Comput. Sci. 12 (1980), 161-173.","journal-title":"Theoret. Comput. Sci."},{"key":"e_1_2_1_2_2","first-page":"431","article-title":"Retativizations of the P = 9NP question","volume":"4","author":"BAKER T. P","year":"1975","unstructured":"BAKER , T. P , GILL , J. , AND SOLOVAY , R.M . Retativizations of the P = 9NP question . SIAM J. Comput. 4 ( 1975 ), 431 - 442 . BAKER, T. P, GILL, J., AND SOLOVAY, R.M. Retativizations of the P = 9NP question. SIAM J. Comput. 4 (1975), 431-442.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_3_2","unstructured":"BALC~ZAR J. L. DIAZ J. AND GABARR() J. Structural Complexity vol. I. Springer-Verlag 1987. BALC~ZAR J. L. DIAZ J. AND GABARR() J. Structural Complexity vol. I. Springer-Verlag 1987."},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","article-title":"Relative to a random oracle A p A #= NpA ~: co_NP.4 with probability 1","author":"BENNET C. H.","year":"1981","unstructured":"BENNET , C. H. , AND GILL , J . Relative to a random oracle A p A #= NpA ~: co_NP.4 with probability 1 . SIAM J. Comput. IO ( 1981 ), 96 - 112 . BENNET, C. H., AND GILL, J. Relative to a random oracle A p A #= NpA ~: co_NP.4 with probability 1. SIAM J. Comput. IO (1981), 96-112.","journal-title":"SIAM J. Comput. IO ("},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","article-title":"Parity circuits, and the polynomial-time hierarchy","volume":"17","author":"FURST M.","year":"1984","unstructured":"FURST , M. , SAXE , J. B. , AND SIPSER , M . Parity circuits, and the polynomial-time hierarchy . Math. Syst. Theory 17 ( 1984 ), 13 - 27 . FURST, M., SAXE, J. B., AND SIPSER, M. Parity circuits, and the polynomial-time hierarchy. Math. Syst. Theory 17 (1984), 13-27.","journal-title":"Math. Syst. Theory"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","article-title":"Computational complexity of probabllistic Turing machines","volume":"6","author":"GILL J","year":"1977","unstructured":"GILL , J . Computational complexity of probabllistic Turing machines . SIAM J. Comput. 6 ( 1977 ), 675 - 695 . GILL, J. Computational complexity of probabllistic Turing machines. SIAM J. Comput. 6 (1977), 675-695.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_8_2","first-page":"73","article-title":"The structural complexity column: Sparse complete sets for NP and the optimal collapse of the polynomial hierarchy","volume":"32","author":"HARTMANIS J","year":"1987","unstructured":"HARTMANIS , J . The structural complexity column: Sparse complete sets for NP and the optimal collapse of the polynomial hierarchy . Bull. EA TCS 32 ( 1987 ), 73 - 81 . HARTMANIS, J. The structural complexity column: Sparse complete sets for NP and the optimal collapse of the polynomial hierarchy. Bull. EA TCS 32 (1987), 73- 81.","journal-title":"Bull. EA TCS"},{"key":"e_1_2_1_10_2","first-page":"251","volume-title":"Proceedings of the 3rd Structure in Complexity Theory Conference. IEEE","author":"K.","year":"1988","unstructured":"Ko, K. Relativized polynommI time hierarchies having exactly K levels . In Proceedings of the 3rd Structure in Complexity Theory Conference. IEEE , New York , 1988 , pp. 251 - 252 . Ko, K. Relativized polynommI time hierarchies having exactly K levels. In Proceedings of the 3rd Structure in Complexity Theory Conference. IEEE, New York, 1988, pp. 251-252."},{"key":"e_1_2_1_11_2","first-page":"446","volume-title":"IEEE","author":"PAPADIMITRIOU C. H.","year":"1983","unstructured":"PAPADIMITRIOU , C. H. Games against nature In Proceedings of the 24th Foundations of Computer Science . IEEE , New York , 1983 , pp. 446 - 450 . PAPADIMITRIOU, C. H. Games against nature In Proceedings of the 24th Foundations of Computer Science. IEEE, New York, 1983, pp. 446-450."},{"key":"e_1_2_1_12_2","series-title":"Lecture Notes in Computer Science","first-page":"269","volume-title":"Proceedings of the 6th GI Conference on Theoretical Computer Science","author":"PAPADIMITRIOU C. H.","year":"1983","unstructured":"PAPADIMITRIOU , C. H. , AND ZACHOS , S. Two remarks on the power of counting . In Proceedings of the 6th GI Conference on Theoretical Computer Science . Lecture Notes in Computer Science , vol. 145 . Springer-Verlag , New York , 1983 , pp. 269 - 276 . PAPADIMITRIOU, C. H., AND ZACHOS, S. Two remarks on the power of counting. In Proceedings of the 6th GI Conference on Theoretical Computer Science. Lecture Notes in Computer Science, vol. 145. Springer-Verlag, New York, 1983, pp. 269-276."},{"key":"e_1_2_1_14_2","series-title":"Lecture Notes in Computer Smence","volume-title":"Complexity and structure","author":"SCH MNG","year":"1985","unstructured":"SCH 6 MNG , U. Complexity and structure . In Lecture Notes in Computer Smence , vol. 211 . Springer-Verlag , New York , 1985 . SCH6MNG, U. Complexity and structure. In Lecture Notes in Computer Smence, vol. 211. Springer-Verlag, New York, 1985."},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","unstructured":"STOCKMEYER L.J. The polynomial time hierarchy. Theoret. Comput. Sci. 3 (i977) 1-22. STOCKMEYER L.J. The polynomial time hierarchy. Theoret. Comput. Sci. 3 (i977) 1-22.","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"e_1_2_1_17_2","first-page":"514","volume-title":"Proceedings of the 30th Foundations of Computer Science. IEEE","author":"TODA S.","year":"1989","unstructured":"TODA , S. On the computational power of PP and ~ P . In Proceedings of the 30th Foundations of Computer Science. IEEE , New York , 1989 , 514 - 519 . TODA, S. On the computational power of PP and ~ P. In Proceedings of the 30th Foundations of Computer Science. IEEE, New York, 1989, 514-519."},{"key":"e_1_2_1_19_2","first-page":"213","volume-title":"Proceedings of the 3rd Structure in Complexity Theory Conference. IEEE","author":"TOR~N J.","year":"1988","unstructured":"TOR~N , J. An oracle characterization of the counting hierarchy . In Proceedings of the 3rd Structure in Complexity Theory Conference. IEEE , New York , 1988 , pp. 213 - 223 TOR~N, J. An oracle characterization of the counting hierarchy. In Proceedings of the 3rd Structure in Complexity Theory Conference. IEEE, New York, 1988, pp. 213-223"},{"key":"e_1_2_1_20_2","first-page":"189","article-title":"The complexW of computing the permanent Theoret","volume":"8","author":"VALIANT L.G","year":"1979","unstructured":"VALIANT , L.G . The complexW of computing the permanent Theoret . Comput. Sci. 8 ( 1979 ), 189 - 201 . VALIANT, L.G. The complexW of computing the permanent Theoret. Comput. Sci. 8 (1979), 189-201.","journal-title":"Comput. Sci."},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289117"},{"key":"e_1_2_1_22_2","volume-title":"Computational complexity. Reidel","author":"WAGNER K.","year":"1986","unstructured":"WAGNER , K. AND WECHSUNG , G. Computational complexity. Reidel ( 1986 ). WAGNER, K. AND WECHSUNG, G. Computational complexity. Reidel (1986)."},{"key":"e_1_2_1_23_2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","article-title":"Complete sets and the polynomial time hmrarchy","volume":"3","author":"WRATHALL C","year":"1977","unstructured":"WRATHALL , C . Complete sets and the polynomial time hmrarchy . Theoret. Comput. Sci. 3 ( 1977 ), 23 - 33 . WRATHALL, C. Complete sets and the polynomial time hmrarchy. Theoret. Comput. Sci. 3 (1977), 23-33.","journal-title":"Theoret. Comput. Sci."},{"key":"e_1_2_1_24_2","first-page":"1","volume-title":"Proceedings of the 26th Annual Foundations of Computer Science. IEEE","author":"YAO A.","year":"1985","unstructured":"YAO , A. Separating the polynomial time hierarchy with oracles . In Proceedings of the 26th Annual Foundations of Computer Science. IEEE , New York , 1985 . pp. 1 - 10 . YAO, A. Separating the polynomial time hierarchy with oracles. In Proceedings of the 26th Annual Foundations of Computer Science. IEEE, New York, 1985. pp. 1-10."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/116825.116858","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:36:59Z","timestamp":1672263419000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/116825.116858"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,7]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1991,7]]}},"alternative-id":["10.1145\/116825.116858"],"URL":"http:\/\/dx.doi.org\/10.1145\/116825.116858","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1991,7]]},"assertion":[{"value":"1991-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}