{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:32:31Z","timestamp":1725456751488},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540529538"},{"type":"electronic","value":"9783540471851"}],"license":[{"start":{"date-parts":[[1990,1,1]],"date-time":"1990-01-01T00:00:00Z","timestamp":631152000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/bfb0029600","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T05:33:46Z","timestamp":1133415226000},"page":"121-134","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Counting the number of solutions"],"prefix":"10.1007","author":[{"given":"Jacobo","family":"Tor\u00e1n","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,11]]},"reference":[{"key":"9_CR1","unstructured":"E. Allender: The complexity of sparse sets in P. Proc. 1st Structure in Complexity Theory Conference, Lect. Notes in Comp. Sci., (1986) 1\u201311."},{"key":"9_CR2","first-page":"49","volume":"40","author":"E. Allender","year":"1990","unstructured":"E. Allender and K. Wagner: Counting hierarchies: polynomial time and constant depth circuits. Bulletin of the EATCS 40, (1990) 49\u201357.","journal-title":"Bulletin of the EATCS"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"J.L. Balc\u00e1zar, J. Diaz, and J. Gabarr\u00f3: Structural Complexity (vol. I). Springer-Verlag (1987).","DOI":"10.1007\/978-3-642-97062-7"},{"key":"9_CR4","unstructured":"R. Beigel: Relativized counting classes: Relations among thresholds, parity and mods. Journal of Comput. Syst. Sci. To appear."},{"key":"9_CR5","unstructured":"R. Beigel: Polynomial interpolation, threshold circuits and the polynomial hierarchy. Manuscript, Jan. 1990."},{"key":"9_CR6","unstructured":"R. Beigel, J. Gill and U. Hertrampf: Counting classes: thresholds, parity mod and fewness. Proc. STACS 90, Lect. Notes in Comp. Sci., (1990) 49\u201357."},{"key":"9_CR7","unstructured":"R. Beigel, L. Hemachandra and G. Wechsung: On the power of probabilistic polynomial time. Proc. 4th Structure in Complexity Theory Conference, IEEE (1989) 225\u2013230."},{"key":"9_CR8","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/S0019-9958(82)90439-9","volume":"55","author":"A. Blass","year":"1982","unstructured":"A. Blass and Y. Gurevich. On the unique satisfiability problem. Information and Control 55 (1982), 80\u201388.","journal-title":"Information and Control"},{"key":"9_CR9","unstructured":"J.Y. Cai, L.A. Hemachandra: On the power of parity polynomial time. Proc. STACS 89, Lect. Notes in Comp. Sci., (1989) 229\u2013239."},{"key":"9_CR10","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"J. Gill: Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6 (1977), 675\u2013695.","journal-title":"SIAM J. Comput."},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"A.V. Goldberg, M. Sipser: Compression and ranking. Proc. 17th STOC Conference (1985), 440\u2013448.","DOI":"10.1145\/22145.22194"},{"key":"9_CR12","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1137\/0214003","volume":"14","author":"K. Ko","year":"1985","unstructured":"K. Ko and U. Sch\u00f6ning: On circuit-size complexity and the low hierarchy in NP. SIAM J. Comput. 14 (1985), 41\u201351.","journal-title":"SIAM J. Comput."},{"key":"9_CR13","unstructured":"J. K\u00f6bler: Strukturelle Komplexit\u00e4t von Anzahlproblemen. Ph.D. Thesis. Universit\u00e4t Suttgart, (1989)."},{"key":"9_CR14","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning, S. Toda, J. Tor\u00e1n: Turing machines with few accepting computations and low sets for PP. Proc. 4th Structure in Complexity Theory Conference, IEEE (1989) 208\u2013216."},{"key":"9_CR15","unstructured":"M.W. Krentel: The complexity of optimization problems. Proc. 18th STOC Conference, (1986) 69\u201376."},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"C.H. Papadimitriou, S. Zachos: Two remarks on the power of counting. 6th GI Conference on Theoret. Comput. Sci., Lect. Notes in Comp. Sci. (1983), 269\u2013276.","DOI":"10.1007\/BFb0009651"},{"key":"9_CR17","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/322290.322306","volume":"29","author":"C. Rackoff","year":"1982","unstructured":"C. Rackoff: Relativized questons involving probabilistic algorithms. J. Assoc. Comput. Math. 29 (1982) 261\u2013268.","journal-title":"J. Assoc. Comput. Math."},{"key":"9_CR18","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/0022-0000(83)90027-2","volume":"27","author":"U. Sch\u00f6ning","year":"1983","unstructured":"U. Sch\u00f6ning: A low and a high hierarchy within NP. Journal Comput. Syst. Sci. 27 (1983), 14\u201328.","journal-title":"Journal Comput. Syst. Sci."},{"key":"9_CR19","unstructured":"U. Sch\u00f6ning: Complexity and structure. Lect. Notes in Comp. Sci. 211, Springer-Verlag (1985)."},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning: Probabilistic complexity classes and lowness. Proc. 2nd Structure in Complexity Theory Conference, IEEE, (1988), 2\u20138.","DOI":"10.1109\/PSCT.1987.10319246"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning: The power of counting. Proc. 3rd Structure in Complexity Theory Conference, IEEE, (1988), 1\u20139.","DOI":"10.1109\/SCT.1988.5257"},{"key":"9_CR22","unstructured":"J. Simon: On some central problems in computational complexity. Ph.D. Thesis, Cornell University (1975)."},{"key":"9_CR23","unstructured":"S. Toda: On the computational power of PP and \u2295P, Proc. 30th FOCS Conference, (1989) 514\u2013519."},{"key":"9_CR24","unstructured":"J. Tor\u00e1n: Structural properties of the counting hierarchies. Ph.D. Thesis. Facultat d'Inform\u00e1tica de Barcelona, (1988)."},{"key":"9_CR25","doi-asserted-by":"crossref","unstructured":"J. Tor\u00e1n: An oracle characterization of the counting hierarchy. Proc. 3rd Structure in Complexity Theory Conference, IEEE, (1988), 213\u2013223","DOI":"10.1109\/SCT.1988.5281"},{"key":"9_CR26","doi-asserted-by":"crossref","unstructured":"J. Tor\u00e1n: A combinatorial technique for separating counting complexity classes. Proc. 16th ICALP Conference, Lecture notes in Comp. Science, (1989), 733\u2013745.","DOI":"10.1007\/BFb0035795"},{"key":"9_CR27","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L. Valiant","year":"1976","unstructured":"L. Valiant: The relative complexity of cheking and evaluating. Inform. Proc. Letters 5 (1976), 20\u201323.","journal-title":"Inform. Proc. Letters"},{"key":"9_CR28","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L. Valiant","year":"1986","unstructured":"L. Valiant and V. Vazirani: NP is as easy as detecting unique solutions. Theoretical Comp. Science 47 (1986), 85\u201393.","journal-title":"Theoretical Comp. Science"},{"key":"9_CR29","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K. Wagner","year":"1986","unstructured":"K. Wagner: The complexity of combinatorial problems with succint input representation. Acta Informatica 23 (1986), 325\u2013356.","journal-title":"Acta Informatica"},{"key":"9_CR30","doi-asserted-by":"crossref","unstructured":"K. Wagner: Bounded query computations. Proc. 3rd Structure in Complexity Theory Conference, IEEE, (1988), 260\u2013277.","DOI":"10.1109\/SCT.1988.5286"},{"key":"9_CR31","unstructured":"K. Wagner and G. Wechsung: Computational complexity. Reidel (1986)."},{"key":"9_CR32","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/S0019-9958(82)80019-3","volume":"54","author":"S. Zachos","year":"1982","unstructured":"S. Zachos: Robustness of probabilistic complexity classes under definitional perturbations. Information an control 54 (1982), 143\u2013154.","journal-title":"Information an control"},{"key":"9_CR33","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0019-9958(86)80044-4","volume":"69","author":"S. Zachos","year":"1986","unstructured":"S. Zachos and H. Heller: A decisive characterization of BPP. Information an control 69 (1986), 125\u2013135.","journal-title":"Information an control"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1990"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0029600","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,1]],"date-time":"2024-02-01T06:47:21Z","timestamp":1706770041000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029600"}},"subtitle":["A survey of recent inclusion results in the area of counting classes"],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540529538","9783540471851"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/bfb0029600","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]},"assertion":[{"value":"11 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}