{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:46:55Z","timestamp":1725536815469},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642038150"},{"type":"electronic","value":"9783642038167"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03816-7_17","type":"book-chapter","created":{"date-parts":[[2009,8,19]],"date-time":"2009-08-19T10:43:03Z","timestamp":1250678583000},"page":"187-198","source":"Crossref","is-referenced-by-count":6,"title":["A Dichotomy Theorem for Polynomial Evaluation"],"prefix":"10.1007","author":[{"given":"Ir\u00e9n\u00e9e","family":"Briquel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Koiran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"17_CR1","first-page":"73","volume":"3","author":"P. B\u00fcrgisser","year":"1999","unstructured":"B\u00fcrgisser, P.: On the structure of Valiant\u2019s complexity classes. Discrete Mathematics and Theoretical Computer Science\u00a03, 73\u201394 (1999)","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"17_CR2","series-title":"Algorithms and Computation in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04179-6","volume-title":"Completeness and Reduction in Algebraic Complexity Theory","author":"P. B\u00fcrgisser","year":"2000","unstructured":"B\u00fcrgisser, P.: Completeness and Reduction in Algebraic Complexity Theory. Algorithms and Computation in Mathematics, vol.\u00a07. Springer, Heidelberg (2000)"},{"key":"17_CR3","unstructured":"Briquel, I., Koiran, P.: A dichotomy theorem for polynomial evaluation, http:\/\/prunel.ccsd.cnrs.fr\/ensl-00360974"},{"issue":"1","key":"17_CR4","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/1120582.1120584","volume":"53","author":"A. Bulatov","year":"2006","unstructured":"Bulatov, A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. Journal of the ACM\u00a053(1), 66\u2013120 (2006)","journal-title":"Journal of the ACM"},{"key":"17_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0016","volume":"125","author":"N. Creignou","year":"1996","unstructured":"Creignou, N., Hermann, M.: Complexity of generalized satisfiability counting problems. Information and Computation\u00a0125, 1\u201312 (1996)","journal-title":"Information and Computation"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity classification of boolean constraint satisfaction problems. SIAM monographs on discrete mathematics (2001)","DOI":"10.1137\/1.9780898718546"},{"issue":"1-3","key":"17_CR7","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S0012-365X(01)00272-2","volume":"250","author":"F.M. Dong","year":"2002","unstructured":"Dong, F.M., Hendy, M.D., Teo, K.L., Little, C.H.C.: The vertex-cover polynomial of a graph. Discrete Mathematics\u00a0250(1-3), 71\u201378 (2002)","journal-title":"Discrete Mathematics"},{"key":"17_CR8","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF01010403","volume":"48","author":"M. Jerrum","year":"1987","unstructured":"Jerrum, M.: Two-dimensional monomer-dimer systems are computationally intractable. Journal of Statistical Physics\u00a048, 121\u2013134 (1987)","journal-title":"Journal of Statistical Physics"},{"key":"17_CR9","series-title":"Lectures in Mathematics - ETH Z\u00fcrich","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8005-3","volume-title":"Counting, Sampling and Integrating : Algorithms and Complexity","author":"M. Jerrum","year":"2003","unstructured":"Jerrum, M.: Counting, Sampling and Integrating: Algorithms and Complexity. Lectures in Mathematics - ETH Z\u00fcrich. Birkh\u00e4user, Basel (2003)"},{"issue":"2","key":"17_CR10","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1137\/0607036","volume":"7","author":"N. Linial","year":"1986","unstructured":"Linial, N.: Hard enumeration problems in geometry and combinatorics. SIAM Journal of Algebraic and Discrete Methods\u00a07(2), 331\u2013335 (1986)","journal-title":"SIAM Journal of Algebraic and Discrete Methods"},{"issue":"1","key":"17_CR11","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/S0196-8858(03)00087-3","volume":"32","author":"M. Lotz","year":"2004","unstructured":"Lotz, M., Makowsky, J.A.: On the algebraic complexity of some families of coloured Tutte polynomials. Advances in Applied Mathematics\u00a032(1), 327\u2013349 (2004)","journal-title":"Advances in Applied Mathematics"},{"issue":"4","key":"17_CR12","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1137\/0212053","volume":"12","author":"J.S. Provan","year":"1983","unstructured":"Provan, J.S., Ball, M.O.: The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. of Comp.\u00a012(4), 777\u2013788 (1983)","journal-title":"SIAM J. of Comp."},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Conference Record of the 10th Symposium on Theory of Computing, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Completeness classes in algebra. In: Proc. 11th ACM Symposium on Theory of Computing, pp. 249\u2013261 (1979)","DOI":"10.1145\/800135.804419"},{"key":"17_CR15","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoretical Computer Science\u00a08, 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"17_CR16","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM Journal of Computing\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM Journal of Computing"},{"issue":"1","key":"17_CR17","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1142\/S0129054191000066","volume":"2","author":"V. Zank\u00f3","year":"1991","unstructured":"Zank\u00f3, V.: #P-completeness via many-one reductions. International Journal of Foundations of Computer Science\u00a02(1), 77\u201382 (1991)","journal-title":"International Journal of Foundations of Computer Science"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03816-7_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T22:33:47Z","timestamp":1558478027000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03816-7_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642038150","9783642038167"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03816-7_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}