{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,16]],"date-time":"2023-02-16T09:31:18Z","timestamp":1676539878133},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,2,25]],"date-time":"2009-02-25T00:00:00Z","timestamp":1235520000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,8]]},"DOI":"10.1007\/s00224-009-9194-6","type":"journal-article","created":{"date-parts":[[2009,2,24]],"date-time":"2009-02-24T16:48:20Z","timestamp":1235494100000},"page":"454-490","source":"Crossref","is-referenced-by-count":6,"title":["The Complexity of Problems for Quantified Constraints"],"prefix":"10.1007","volume":"47","author":[{"given":"Michael","family":"Bauland","sequence":"first","affiliation":[]},{"given":"Elmar","family":"B\u00f6hler","sequence":"additional","affiliation":[]},{"given":"Nadia","family":"Creignou","sequence":"additional","affiliation":[]},{"given":"Steffen","family":"Reith","sequence":"additional","affiliation":[]},{"given":"Henning","family":"Schnoor","sequence":"additional","affiliation":[]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,2,25]]},"reference":[{"key":"9194_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1007\/3-540-45294-X_6","volume-title":"Proceedings 21st Foundations of Software Technology and Theoretical Computer Science","author":"M. Agrawal","year":"2001","unstructured":"Agrawal, M.: The first-order isomorphism theorem. In: Proceedings 21st Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science, pp. 58\u201369. Springer, Berlin (2001)"},{"key":"9194_CR2","doi-asserted-by":"crossref","unstructured":"Allender, E., Bauland, M., Immerman, N., Schnoor, H., Vollmer, H.: The complexity of satisfiability problems: Refining Schaefer\u2019s theorem. In: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, pp.\u00a071\u201382 (2005)","DOI":"10.1007\/11549345_8"},{"key":"9194_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1007\/11527695_3","volume-title":"Proceedings 7th International Conference on Theory and Applications of Satisfiability Testing, Revised Selected Papers","author":"M. Bauland","year":"2005","unstructured":"Bauland, M., Chapdelaine, P., Creignou, N., Hermann, M., Vollmer, H.: An algebraic approach to the complexity of generalized conjunctive queries. In: Proceedings 7th International Conference on Theory and Applications of Satisfiability Testing, Revised Selected Papers. Lecture Notes in Computer Science, vol. 3542, pp. 30\u201345. Springer, Berlin (2005)"},{"key":"9194_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1007\/3-540-45793-3_28","volume-title":"Computer Science Logic","author":"E. B\u00f6hler","year":"2002","unstructured":"B\u00f6hler, E., Hemaspaandra, E., Reith, S., Vollmer, H.: Equivalence and isomorphism for Boolean constraint satisfaction. In: Computer Science Logic. Lecture Notes in Computer Science, vol. 2471, pp. 412\u2013426. Springer, Berlin (2002)"},{"issue":"4","key":"9194_CR5","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1145\/954092.954101","volume":"34","author":"E. B\u00f6hler","year":"2003","unstructured":"B\u00f6hler, E., Creignou, N., Reith, S., Vollmer, H.: Playing with Boolean blocks, part I: Post\u2019s lattice with applications to complexity theory. SIGACT News 34(4), 38\u201352 (2003)","journal-title":"SIGACT News"},{"issue":"1","key":"9194_CR6","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/970831.970840","volume":"35","author":"E. B\u00f6hler","year":"2004","unstructured":"B\u00f6hler, E., Creignou, N., Reith, S., Vollmer, H.: Playing with Boolean blocks, part II: Constraint satisfaction problems. SIGACT News 35(1), 22\u201335 (2004)","journal-title":"SIGACT News"},{"key":"9194_CR7","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.ipl.2005.06.003","volume":"96","author":"E. B\u00f6hler","year":"2005","unstructured":"B\u00f6hler, E., Reith, S., Schnoor, H., Vollmer, H.: Bases for Boolean co-clones. Inf. Process. Lett. 96, 59\u201366 (2005)","journal-title":"Inf. Process. Lett."},{"key":"9194_CR8","unstructured":"B\u00f6rner, F., Krokhin, A., Bulatov, A., Jeavons, P.: Quantified constraints and surjective polymorphisms. Technical Report PRG-RR-02-11, Computing Laboratory, University of Oxford, UK (2002)"},{"key":"9194_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/b94014","volume-title":"Proceedings 17th International Workshop on Computer Science Logic","author":"F. B\u00f6rner","year":"2003","unstructured":"B\u00f6rner, F., Bulatov, A., Jeavons, P., Krokhin, A.: Quantified constraints: algorithms and complexity. In: Proceedings 17th International Workshop on Computer Science Logic. Lecture Notes in Computer Science, vol. 2803. Springer, Berlin (2003)"},{"issue":"1","key":"9194_CR10","first-page":"66","volume":"53","author":"A.A. Bulatov","year":"2006","unstructured":"Bulatov, A.A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J.\u00a0ACM 53(1), 66\u2013120 (2006)","journal-title":"J.\u00a0ACM"},{"issue":"5","key":"9194_CR11","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1016\/j.ic.2006.09.005","volume":"205","author":"A. Bulatov","year":"2007","unstructured":"Bulatov, A., Dalmau, V.: Towards a dichotomy theorem for the counting constraint satisfaction problem. Inf. Comput. 205(5), 651\u2013678 (2007)","journal-title":"Inf. Comput."},{"key":"9194_CR12","first-page":"155","volume-title":"Proceedings of the Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial","author":"H. Chen","year":"2004","unstructured":"Chen, H.: Collapsibility and consistency in quantified constraint satisfaction. In: Proceedings of the Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial, pp. 155\u2013160. AAAI Press, Menlo Prak (2004)"},{"key":"9194_CR13","unstructured":"Chen, H.: The computational complexity of quantified constraint satisfaction. Ph.D. thesis, Cornell Universtiy (2004)"},{"issue":"4","key":"9194_CR14","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1145\/1189056.1189076","volume":"37","author":"H. Chen","year":"2006","unstructured":"Chen, H.: A rendezvous of logic, complexity, and algebra. ACM-SIGACT Newsl. 37(4), 85\u2013114 (2006)","journal-title":"ACM-SIGACT Newsl."},{"key":"9194_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/11576259","volume-title":"Proceedings 19th International Workshop on Computer Science Logic","author":"H. Chen","year":"2005","unstructured":"Chen, H., Dalmau, V.: From pebble games to tractability: An ambidextrous consistency algorithm for quantified constraint satisfaction. In: Proceedings 19th International Workshop on Computer Science Logic. Lecture Notes in Computer Science, vol. 3634, pp. 232\u2013247. Springer, Berlin (2005)"},{"key":"9194_CR16","first-page":"151","volume-title":"Proceedings 3rd Symposium on Theory of Computing","author":"S.A. Cook","year":"1971","unstructured":"Cook, S.A.: The complexity of theorem proving procedures. In: Proceedings 3rd Symposium on Theory of Computing, pp. 151\u2013158. ACM, New York (1971)"},{"key":"9194_CR17","doi-asserted-by":"crossref","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. Inf. Comput. 125, 1\u201312 (1996)","journal-title":"Inf. Comput."},{"key":"9194_CR18","series-title":"Monographs on Discrete Applied Mathematics","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718546","volume-title":"Complexity Classifications of Boolean Constraint Satisfaction Problems","author":"N. Creignou","year":"2001","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. Monographs on Discrete Applied Mathematics. SIAM, Philadelphia (2001)"},{"key":"9194_CR19","series-title":"Lecture Notes in Computer Science","volume-title":"Complexity of Constraints\u2014An Overview of Current Research Themes","year":"2008","unstructured":"Creignou, N., Kolaitis, P., Vollmer, H. (Eds.): Complexity of Constraints\u2014An Overview of Current Research Themes. Lecture Notes in Computer Science, vol. 5250. Springer, Berlin (2008)"},{"key":"9194_CR20","doi-asserted-by":"crossref","unstructured":"Dalmau, V.: Some dichotomy theorems on constant-free quantified boolean formulas. Technical Report LSI-97-43-R, Department de Llenguatges i Sistemes Inform\u00e0tica, Universitat Polit\u00e9cnica de Catalunya (1997)","DOI":"10.1145\/267460.267496"},{"key":"9194_CR21","unstructured":"Dalmau, V.: Computational complexity of problems over generalized formulas. Ph.D. thesis, Department de Llenguatges i Sistemes Inform\u00e0tica, Universitat Polit\u00e9cnica de Catalunya (2000)"},{"issue":"3","key":"9194_CR22","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1016\/j.tcs.2005.03.012","volume":"340","author":"A. Durand","year":"2005","unstructured":"Durand, A., Hermann, M., Kolaitis, P.G.: Subtractive reductions and complete problems for counting complexity classes. Theor. Comput. Sci. 340(3), 496\u2013513 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9194_CR23","unstructured":"Hemaspaandra, E.: Dichotomy theorems for alternation-bounded quantified boolean formulas. CoRR, cs.CC\/0406006 (2004)"},{"issue":"1","key":"9194_CR24","first-page":"2","volume":"26","author":"L. Hemaspaandra","year":"1995","unstructured":"Hemaspaandra, L., Vollmer, H.: The satanic notations: counting classes beyond #P and other definitional adventures. Complexity Theory Column 8, ACM-SIGACT News 26(1), 2\u201313 (1995)","journal-title":"Complexity Theory Column 8, ACM-SIGACT News"},{"issue":"4","key":"9194_CR25","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P. Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: Closure properties of constraints. J. ACM 44(4), 527\u2013548 (1997)","journal-title":"J. ACM"},{"key":"9194_CR26","series-title":"Cambridge Tracts in Theoretical Computer Science","volume-title":"Propositional Logic: Deduction and Algorithms","author":"H. Kleine B\u00fcning","year":"1999","unstructured":"Kleine B\u00fcning, H., Lettmann, T.: Propositional Logic: Deduction and Algorithms. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge (1999)"},{"issue":"6","key":"9194_CR27","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1137\/0218073","volume":"18","author":"R.E. Ladner","year":"1989","unstructured":"Ladner, R.E.: Polynomial space counting problems. SIAM J. Comput. 18(6), 1087\u20131097 (1989)","journal-title":"SIAM J. Comput."},{"key":"9194_CR28","series-title":"Monographs in Mathematics","volume-title":"Function Algebras on Finite Sets","author":"D. Lau","year":"2006","unstructured":"Lau, D.: Function Algebras on Finite Sets. Monographs in Mathematics. Springer, Berlin (2006)"},{"issue":"3","key":"9194_CR29","first-page":"115","volume":"9","author":"L.A. Levin","year":"1973","unstructured":"Levin, L.A.: Universal sorting problems. Probl. Pered. Inf. 9(3), 115\u2013116 (1973). English translation: Problems Inf. Transm. 9(3), 265\u2013266 (1993)","journal-title":"Probl. Pered. Inf."},{"key":"9194_CR30","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1109\/SWAT.1972.29","volume-title":"Proceedings 13th Symposium on Switching and Automata Theory","author":"A.R. Meyer","year":"1972","unstructured":"Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential time. In: Proceedings 13th Symposium on Switching and Automata Theory, pp. 125\u2013129. IEEE Computer Society Press, Los Alamitos (1972)"},{"key":"9194_CR31","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"9194_CR32","volume-title":"Theories of Computability","author":"N. Pippenger","year":"1997","unstructured":"Pippenger, N.: Theories of Computability. Cambridge University Press, Cambridge (1997)"},{"key":"9194_CR33","unstructured":"P\u00f6schel, R.: Galois connection for operations and relations. Technical Report MATH-LA-8-2001, Technische Universit\u00e4t Dresden (2001)"},{"key":"9194_CR34","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0348-5547-1","volume-title":"Funktionen- und Relationenalgebren","author":"R. P\u00f6schel","year":"1979","unstructured":"P\u00f6schel, R., Kalu\u017enin, L.A.: Funktionen- und Relationenalgebren. Deutscher Verlag der Wissenschaften, Berlin (1979)"},{"key":"9194_CR35","doi-asserted-by":"crossref","first-page":"163","DOI":"10.2307\/2370324","volume":"43","author":"E.L. Post","year":"1921","unstructured":"Post, E.L.: Introduction to a general theory of elementary propositions. Am. J. Math. 43, 163\u2013185 (1921)","journal-title":"Am. J. Math."},{"key":"9194_CR36","first-page":"1","volume":"5","author":"E. Post","year":"1941","unstructured":"Post, E.: The two-valued iterative systems of mathematical logic. Ann. Math. Stud. 5, 1\u2013122 (1941)","journal-title":"Ann. Math. Stud."},{"key":"9194_CR37","first-page":"376","volume-title":"Proceedings 37th Symposium on Theory of Computing","author":"O. Reingold","year":"2005","unstructured":"Reingold, O.: Undirected ST-connectivity in log-space. In: Proceedings 37th Symposium on Theory of Computing, pp. 376\u2013385. ACM, New York (2005)"},{"key":"9194_CR38","first-page":"216","volume-title":"Proceedings 10th Symposium on Theory of Computing","author":"T.J. Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings 10th Symposium on Theory of Computing, pp. 216\u2013226. ACM, New York (1978)"},{"key":"9194_CR39","doi-asserted-by":"crossref","unstructured":"Schnoor, H., Schnoor, I.: Partial polymorphisms and constraint satisfaction problems. In: [19], pp.\u00a0229\u2013254","DOI":"10.1007\/978-3-540-92800-3_9"},{"key":"9194_CR40","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1977","unstructured":"Stockmeyer, L.: The polynomial-time hierarchy. Theor. Comput. Sci. 3, 1\u201322 (1977)","journal-title":"Theor. Comput. Sci."},{"key":"9194_CR41","first-page":"1","volume-title":"Proceedings 5th ACM Symposium on the Theory of Computing","author":"L.J. Stockmeyer","year":"1973","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time. In: Proceedings 5th ACM Symposium on the Theory of Computing, pp. 1\u20139. ACM, New York (1973)"},{"key":"9194_CR42","unstructured":"Toda, S.: Computational complexity of counting complexity classes. Ph.D. thesis, Tokyo Institute of Technology, Department of Computer Science, Tokyo (1991)"},{"key":"9194_CR43","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial time hierarchy. SIAM J. Comput. 20, 865\u2013877 (1991)","journal-title":"SIAM J. Comput."},{"key":"9194_CR44","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0304-3975(92)90369-Q","volume":"100","author":"S. Toda","year":"1992","unstructured":"Toda, S., Watanabe, O.: Polynomial time 1-Turing reductions from #PH to #P. Theor. Comput. Sci. 100, 205\u2013221 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"9194_CR45","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 8, 189\u2013201 (1979)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9194_CR46","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 411\u2013421 (1979)","journal-title":"SIAM J. Comput."},{"key":"9194_CR47","unstructured":"Vollmer, H.: Komplexit\u00e4tsklassen von Funktionen. Ph.D. thesis, Universit\u00e4t W\u00fcrzburg, Institut f\u00fcr Informatik, Germany (1994)"},{"key":"9194_CR48","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1977","unstructured":"Wrathall, C.: Complete sets and the polynomial-time hierarchy. Theor. Comput. Sci. 3, 23\u201333 (1977)","journal-title":"Theor. Comput. Sci."},{"key":"9194_CR49","doi-asserted-by":"crossref","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. Int. J. Found. Comput. Sci. 2, 77\u201382 (1991)","journal-title":"Int. J. Found. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9194-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-009-9194-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9194-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:51:37Z","timestamp":1558684297000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-009-9194-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2,25]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["9194"],"URL":"https:\/\/doi.org\/10.1007\/s00224-009-9194-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,2,25]]}}}