{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:26:36Z","timestamp":1787509596804,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540164869","type":"print"},{"value":"9783540398257","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16486-3_112","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T13:46:23Z","timestamp":1330177583000},"page":"383-400","source":"Crossref","is-referenced-by-count":23,"title":["Probabilistic quantifiers, adversaries, and complexity classes : An overview"],"prefix":"10.1007","author":[{"given":"Stathis","family":"Zachos","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"28_CR1","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0304-3975(80)90027-4","volume":"12","author":"D. Angluin","year":"1980","unstructured":"ANGLUIN, D., On counting problems and the polynomial time hierarchy, TCS 12, (1980), 161\u2013173.","journal-title":"TCS"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"BABAI, L., Trading Group Theory for Randomness, 17th STOC, (1985), 421\u2013429.","DOI":"10.1145\/22145.22192"},{"key":"28_CR3","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C.H. Bennett","year":"1981","unstructured":"BENNETT, C.H., and GILL, J., Relative to Random Oracle A, P A \u2260 NP A \u2260 co-NP A , SIAM J. Comput 10, (1981), 96\u2013113.","journal-title":"SIAM J. Comput"},{"key":"28_CR4","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"BAKER, T., GILL, J., and SOLOVAY, R., Relativization of the P=? NP question, SIAM J. of Computing 4, (1975), 431\u2013442.","journal-title":"SIAM J. of Computing"},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"BACH, E., MILLER, G., and SHALLIT, J., Sums of divisors, perfect numbers, and factoring, 16th STOC, (1984), 183\u2013190.","DOI":"10.1145\/800057.808680"},{"key":"28_CR6","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0304-3975(79)90043-4","volume":"8","author":"T. Baker","year":"1979","unstructured":"BAKER, T., and SELMAN, A., A second step toward the polynomial hierarchy, TCS 8, (1979), 177\u2013187.","journal-title":"TCS"},{"key":"28_CR7","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"GILL, J., Computational Complexity of Probabilistic Turing Machines, SIAM J. of Computing 6, (1977), 675\u2013695.","journal-title":"SIAM J. of Computing"},{"key":"28_CR8","doi-asserted-by":"crossref","unstructured":"GALIL, Z., HABER, S., and YUNG, M., A Private Interactive Test of a Boolean Predicate and Minimum \u2014 Knowledge Public \u2014 Key Cryptosystems, 26th FOCS, (1985), 360\u2013371.","DOI":"10.1109\/SFCS.1985.1"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"GOLDWASSER, S., MICALI, S., and RACKOFF, C., The Knowledge Complexity of Interactive Proof Systems, 17th STOC, (1985), 291\u2013304.","DOI":"10.1145\/22145.22178"},{"key":"28_CR10","unstructured":"GOLDWASSER, S., and SIPSER, M., Arthur Merlin Games versus Interactive Proof Systems, 18th STOC, (1986)."},{"key":"28_CR11","doi-asserted-by":"crossref","unstructured":"HELLER, H., On relativized exponential and probabilistic complexity classes, (1985), submitted to Information and Control.","DOI":"10.1016\/S0019-9958(86)80012-2"},{"key":"28_CR12","volume-title":"Topics in Probabilistic Complexity","author":"J.W. Hunt","year":"1978","unstructured":"HUNT, J.W., Topics in Probabilistic Complexity, Ph.D. Dissertation, Department of Electrical Engineering, Stanford, (1978)."},{"key":"28_CR13","doi-asserted-by":"crossref","unstructured":"HINMAN, P. and ZACHOS, S., Probabilistic Machines, Oracles and Quantifiers, Proceedings of the Oberwolfach Recursion-theoretic Week, Lecture Notes in Mathematics, 1141, Springer-Verlag, (1984), 159\u2013192.","DOI":"10.1007\/BFb0076220"},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"KER-I-KO, Some Observations on Probabilistic Algorithms and NP-Hard Problems, IPL 14, (1982), 39\u201343.","DOI":"10.1016\/0020-0190(82)90139-9"},{"key":"28_CR15","doi-asserted-by":"crossref","unstructured":"PAPADIMITRIOU, C.H., Games against Nature, 24th FOCS, (1983), 446\u2013450.","DOI":"10.1109\/SFCS.1983.20"},{"key":"28_CR16","doi-asserted-by":"crossref","unstructured":"PAPADIMITRIOU, C.H., and YANNAKAKIS, M., The Complexity of Facets (and some facets of complexity), 14th STOC, (1982), 255\u2013260.","DOI":"10.1145\/800070.802199"},{"key":"28_CR17","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1016\/0022-314X(80)90084-0","volume":"12","author":"M. Rabin","year":"1980","unstructured":"RABIN, M., Probabilistic Algorithm for Testing Primality, J. of Number Theory 12, (1980), 128\u2013138.","journal-title":"J. of Number Theory"},{"key":"28_CR18","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/322290.322306","volume":"29","author":"C. Rackoff","year":"1982","unstructured":"RACKOFF, C., Relativized questions involving probabilistic algorithms, JACM 29, (1982), 261\u2013268.","journal-title":"JACM"},{"key":"28_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1976","unstructured":"STOCKMEYER, L.J., The Polynomial-Time Hierarchy, TCS 3, (1976), 1\u201322.","journal-title":"TCS"},{"key":"28_CR20","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1137\/0206006","volume":"6","author":"R. Solovay","year":"1977","unstructured":"SOLOVAY, R., and STRASSEN, V., A fast Monte-Carlo test for primality, SIAM J. of Computing 6, (1977) 84\u201385.","journal-title":"SIAM J. of Computing"},{"key":"28_CR21","doi-asserted-by":"crossref","unstructured":"VAZIRANI, U.V., and VAZIRANI, V.V., Random polynomial time is equal to slightly random polynomial time, 26th FOCS, (1985), 417\u2013428.","DOI":"10.1109\/SFCS.1985.45"},{"key":"28_CR22","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1976","unstructured":"WRATHALL, C., Complete sets and the polynomial-time hierarchy, TCS 3, (1976), 23\u201333.","journal-title":"TCS"},{"key":"28_CR23","doi-asserted-by":"crossref","unstructured":"YAO, A.C., Separating the Polynomial \u2014 Time Hierarchy by Oracles, 26th FOCS, (1985), 1\u201310.","DOI":"10.1109\/SFCS.1985.49"},{"key":"28_CR24","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/S0019-9958(82)80019-3","volume":"54","author":"S. Zachos","year":"1982","unstructured":"ZACHOS, S., Robustness of Probabilistic Computational Complexity Classes under Definitional Perturbations, Information and Control, (1982), 54, 143\u2013154.","journal-title":"Information and Control"},{"key":"28_CR25","unstructured":"ZACHOS, S., Collapsing probabilistic polynomial hierarchies, Proc. Conf. on Computational Complexity Theory, Santa Barbara, (1983), 75\u201381."},{"key":"28_CR26","unstructured":"ZACHOS, S., and FURER, M., Probabilistic Quantifiers vs. Distrustful Adversaries, (1985), submitted for publication."},{"key":"28_CR27","unstructured":"ZACHOS, S., and HELLER, H., On BPP, TM-252, LCS, MIT, (1983)."},{"key":"28_CR28","doi-asserted-by":"crossref","unstructured":"ZACHOS, S., and HELLER, H., A Decisive Characterization of BPP, (1984), to appear in Information and Control.","DOI":"10.1007\/3-540-13883-8_72"}],"container-title":["Lecture Notes in Computer Science","Structure in Complexity Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16486-3_112.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,30]],"date-time":"2021-12-30T20:45:21Z","timestamp":1640897121000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16486-3_112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540164869","9783540398257"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-16486-3_112","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986]]}}}