{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:26:58Z","timestamp":1787340418510,"version":"build-2736575974"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>An equality template is a relational structure with infinite universe whose relations can be defined by Boolean combinations of equalities. We prove a complexity classification for quantified constraint satisfaction problems (QCSPs) over equality templates: These problems are in L (decidable in logarithmic space), NP-hard, or coNP-hard. To establish our classification theorem we combine methods from universal algebra with concepts from model theory.<\/jats:p>","DOI":"10.1137\/080725209","type":"journal-article","created":{"date-parts":[[2010,11,17]],"date-time":"2010-11-17T18:05:33Z","timestamp":1290017133000},"page":"3682-3699","source":"Crossref","is-referenced-by-count":15,"title":["Quantified Equality Constraints"],"prefix":"10.1137","volume":"39","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hubie","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,11,17]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"L. Barto and M. Kozik,\n                      Constraint satisfaction problems of bounded width\n                      , in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 2009, pp. 595\u2013603.","DOI":"10.1109\/FOCS.2009.32"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"M. Bodirsky and H. Chen,\n                      Collapsibility in infinite-domain quantified constraint satisfaction\n                      , in Computer Science Logic, Lecture Notes in Comput. Sci. 4207, Springer, Berlin, 2006.","DOI":"10.1007\/11874683_13"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1286198146"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9083-9"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exi083"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"F. Boerner, A. Bulatov, A. Krokhin, and P. Jeavons,\n                      Quantified constraints: Algorithms and complexity\n                      , in Proceedings of CSL'03, Lecture Notes in Comput. Sci. 2803, Springer, Heidelberg, 2003, pp. 58\u201370.","DOI":"10.1007\/978-3-540-45220-1_6"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"A. Bulatov,\n                      Tractable conservative constraint satisfaction problems\n                      , in Proceedings of LICS'03, IEEE Computer Society, Los Alamitos, CA, 2003, pp. 321\u2013330.","DOI":"10.1109\/LICS.2003.1210072"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/050628957"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"N. Creignou, S. Khanna, and M. Sudan,\n                      Complexity Classifications of Boolean Constraint Satisfaction Problems\n                      , SIAM Monogr. Discrete Math. Appl. 7, SIAM, Philadelphia, 2001.","DOI":"10.1137\/1.9780898718546"},{"key":"R11","unstructured":"M. Garey and D. Johnson,\n                      A Guide to NP-Completeness\n                      , CSLI Press, Stanford, CA, 1978."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1994-054-1"},{"key":"R13","unstructured":"P. Hell and J. Ne\u0161et\u0159il,\n                      Graphs and Homomorphisms\n                      , Oxford Lecture Ser. Math. Appl. 28, Oxford University Press, Oxford, 2004."},{"key":"R14","unstructured":"W. Hodges,\n                      A Shorter Model Theory\n                      , Cambridge University Press, Cambridge, UK, 1997."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"P. M. Idziak, P. Markovic, R. McKenzie, M. Valeriote, and R. Willard,\n                      Tractability and learnability arising from algebras with few subpowers\n                      , in Proceedings of LICS'07, IEEE Computer Society, Los Alamitos, CA, 2007, pp. 213\u2013224.","DOI":"10.1109\/LICS.2007.50"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1965-0170812-4"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"E. W. Kiss and M. Valeriote,\n                      On tractability and congruence distributivity\n                      , in Proceedings of LICS'06, IEEE Computer Society, Los Alamitos, CA, 2006, pp. 221\u2013230.","DOI":"10.1109\/LICS.2006.40"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1147\/rd.254.0327"},{"key":"R21","first-page":"61","volume":"6","author":"Mal'tsev A. I.","year":"1967","journal-title":"Algebra i Logika Sem."},{"key":"R22","unstructured":"D. Marker,\n                      Model Theory: An Introduction\n                      , Grad Texts in Math. 217, Springer-Verlag, New York, 2002."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-008-2122-9"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"O. Reingold,\n                      Undirected st-connectivity in log-space\n                      , in Proceedings of the Symposium on Theory of Computing (STOC), ACM, New York, 2005, pp. 376\u2013385.","DOI":"10.1145\/1060590.1060647"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"T. J. Schaefer,\n                      The complexity of satisfiability problems\n                      , in Proceedings of the Symposium on Theory of Computing (STOC), ACM, New York, 1978, pp. 216\u2013226.","DOI":"10.1145\/800133.804350"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"L. J. Stockmeyer and A. R. Meyer,\n                      Word problems requiring exponential time: Preliminary report\n                      , in Proceedings of the Symposium on Theory of Computing (STOC), ACM, New York, 1973, pp. 1\u20139.","DOI":"10.1145\/800125.804029"},{"key":"R27","unstructured":"A. Szendrei,\n                      Clones in Universal Algebra\n                      , S\u00e9m. Math. Sup. 99, Les Presses de L'Universit\u00e9 de Montr\u00e9al, Montreal, QC, 1986."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080725209","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:34:13Z","timestamp":1787337253000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080725209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":27,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080725209"],"URL":"https:\/\/doi.org\/10.1137\/080725209","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}