Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-18T22:58:58.622Z Has data issue: false hasContentIssue false
  • English
  • Français

THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA

Published online by Cambridge University Press:  15 September 2015

LIBOR BARTO
LIBOR BARTO*
Affiliation:
DEPARTMENT OF ALGEBRA FACULTY OF MATHEMATICS AND PHYSICS CHARLES UNIVERSITY IN PRAGUE SOKOLOVSKÁ 83 18675 PRAHA 8, CZECH REPUBLICE-mail: [email protected]: http://www.karlin.mff.cuni.cz/∼barto
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper gives a brief survey of current research on the complexity of the constraint satisfaction problem over fixed constraint languages.

Keywords

68Q2508A7008B05constraint satisfaction problemuniversal algebra
Type
Articles
Information
Bulletin of Symbolic Logic , Volume 21 , Issue 3 , September 2015 , pp. 319 - 337
Copyright
Copyright © The Association for Symbolic Logic 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Arora, Sanjeev and Barak, Boaz, Computational Complexity: A Modern Approach, first edition, Cambridge University Press, New York, NY, USA, 2009.CrossRefGoogle Scholar
Barto, Libor, The dichotomy for conservative constraint satisfaction problems revisited, 26th Annual IEEE Symposium on Logic in Computer Science—LICS 2011, IEEE Computer Society, Los Alamitos, CA, 2011, pp. 301–310.Google Scholar
Barto, Libor, Constraint satisfaction problem and universal algebra, ACM SIGLOG News, vol. 1 (2014), no. 2, pp. 14–24.CrossRefGoogle Scholar
Barto, Libor, The collapse of the bounded width hierarchy. Journal of Logic and Computation, published online 2014.Google Scholar
Barto, Libor, Congruence distributivity implies bounded width. SIAM Journal on Computing, vol. 39 (2009), no. 4, pp. 1531–1542.CrossRefGoogle Scholar
Barto, Libor and Kozik, Marcin, Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem. Logical Methods in Computer Science, vol. 8 (2012), no. 1, pp. 1–26.Google Scholar
Barto, Libor and Kozik, Marcin, Robust satisfiability of constraint satisfaction problems, Proceedings of the 44th Symposium on Theory of Computing (New York, NY, USA), STOC ’12, ACM, 2012, pp. 931–940.CrossRefGoogle Scholar
Barto, Libor and Kozik, Marcin, Constraint satisfaction problems solvable by local consistency methods. Journal of ACM, vol. 61 (2014), no. 1, pp. 3:1–3:19.CrossRefGoogle Scholar
Barto, Libor, Kozik, Marcin, and Niven, Todd, The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell). SIAM Journal on Computing, vol. 38 (2008/09), no. 5, pp. 1782–1802.CrossRefGoogle Scholar
Berman, Joel, Idziak, Pawel, Marković, Petar, McKenzie, Ralph, Valeriote, Matthew, and Willard, Ross, Varieties with few subalgebras of powers. Transactions of the American Mathematical Society, vol. 362 (2009), pp. 1445–1473.CrossRefGoogle Scholar
Birkhoff, Garrett, On the structure of abstract algebras. Proceedings of the Cambridge Philosophical Society, vol. 31 (1935), pp. 433–454.CrossRefGoogle Scholar
Bodirsky, Manuel, Constraint satisfaction problems with infinite templates, Complexity of Constraints (Creignou, Nadia, Kolaitis, Phokion G., and Vollmer, Heribert, editors), Lecture Notes in Computer Science, vol. 5250, Springer, 2008, pp. 196–228.Google Scholar
Bodnarčuk, V. G., Kalužnin, L. A., Kotov, V. N., and Romov, B. A., Galois theory for Post algebras. I, II, Kibernetika (Kiev), (1969), no. 3, pp. 1–10; ibid. 1969, no. 5, pp. 1–9.Google Scholar
Bulatov, Andrei, Bounded relational width, manuscript, 2009.Google Scholar
Bulatov, Andrei and Dalmau, Víctor, A simple algorithm for Mal′tsev constraints. SIAM Journal on Computing, vol. 36 (2006), no. 1, pp. 16–27 (electronic).CrossRefGoogle Scholar
Bulatov, Andrei, Jeavons, Peter, and Krokhin, Andrei, Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, vol. 34 (2005), pp. 720–742.CrossRefGoogle Scholar
Bulatov, Andrei A., Mal’tsev constraints are tractable. Electronic Colloquium on Computational Complexity (ECCC), vol. 34 (2002), pp. 1–37. http://eccc.hpi-web.de/eccc-reports/2002/TR02-034/index.html.Google Scholar
Bulatov, Andrei A., Tractable conservative constraint satisfaction problems, Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science (Washington, DC, USA), IEEE Computer Society, 2003, pp. 321–330.Google Scholar
Bulatov, Andrei A., A graph of a relational structure and constraint satisfaction problems, Proceedings of the Nineteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2004), IEEE Computer Society Press, July 2004, pp. 448–457.CrossRefGoogle Scholar
Bulatov, Andrei A., Combinatorial problems raised from 2-semilattices. Journal of Algebra, vol. 298 (2006), no. 2, pp. 321–339.CrossRefGoogle Scholar
Bulatov, Andrei A., Complexity of conservative constraint satisfaction problems. ACM Transactions on Computational Logic, vol. 12 (2011), no. 4, pp. 24:1–24:66.CrossRefGoogle Scholar
Bulatov, Andrei A., The complexity of the counting constraint satisfaction problem. Journal of ACM, vol. 60 (2013), no. 5, pp. 34:1–34:41.CrossRefGoogle Scholar
Bulatov, Andrei A., Krokhin, Andrei, and Larose, Benoit, Complexity of Constraints(Creignou, Nadia, Kolaitis, Phokion G., and Vollmer, Heribert, editors), Springer-Verlag, Berlin, Heidelberg, 2008, pp. 93–124.CrossRefGoogle Scholar
Buntrock, Gerhard, Damm, Carsten, Hertrampf, Ulrich, and Meinel, Christoph, Structure and importance of logspace-mod class. Mathematical Systems Theory, vol. 25 (1992), no. 3, pp. 223–237 (English).CrossRefGoogle Scholar
Cai, Jin-Yi and Chen, Xi, Complexity of counting csp with complex weights, Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC ’12, ACM, 2012, pp. 909–920.Google Scholar
Carvalho, Catarina, Dalmau, Víctor, Marković, Petar, and Maróti, Miklós, CD(4) has bounded width. Algebra Universalis, vol. 60 (2009), no. 3, pp. 293–307.CrossRefGoogle Scholar
Chen, Hubie, Meditations on quantified constraint satisfaction, Logic and Program Semantics (Constable, Robert L. and Silva, Alexandra, editors), Lecture Notes in Computer Science, vol. 7230, Springer Berlin Heidelberg, 2012, pp. 35–49 (English).CrossRefGoogle Scholar
Cohen, David A., Cooper, Martin C., Creed, Páidí, Jeavons, Peter, and Živný, Stanislav, An algebraic theory of complexity for discrete optimisation. SIAM Journal on Computing, vol. 42 (2013), no. 5, pp. 1915–1939.CrossRefGoogle Scholar
Dalmau, Víctor, Generalized majority-minority operations are tractable, Logical Methods in Computer Science, vol. 2 (2006), no. 4, pp. 4:1, 14.Google Scholar
Dyer, Martin E. and Richerby, David, An effective dichotomy for the counting constraint satisfaction problem. SIAM Journal on Computing, vol. 42 (2013), no. 3, pp. 1245–1274.CrossRefGoogle Scholar
Feder, Tomás and Vardi, Moshe Y., The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory. SIAM Journal on Computing, vol. 28 (1998), no. 1, pp. 57–104.CrossRefGoogle Scholar
Geiger, David, Closed systems of functions and predicates. Pacific Journal of Mathematics, vol. 27 (1968), pp. 95–100.CrossRefGoogle Scholar
Håstad, Johan, On the efficient approximability of constraint satisfaction problems, Surveys in Combinatorics 2007, London Mathematical Society Lecture Note Series, vol. 346, Cambridge University Press, Cambridge, 2007, pp. 201–221.CrossRefGoogle Scholar
Hell, Pavol and Nešetřil, Jaroslav, On the complexity of H-coloring. Journal of Combinatorial Theory, Series B, vol. 48 (1990), no. 1, pp. 92–110.CrossRefGoogle Scholar
Hobby, David and McKenzie, Ralph, The structure of finite algebras, Contemporary Mathematics, vol. 76, American Mathematical Society, Providence, RI, 1988.Google Scholar
Idziak, Pawel, Marković, Petar, McKenzie, Ralph, Valeriote, Matthew, and Willard, Ross, Tractability and learnability arising from algebras with few subpowers, Proceedings of the Twenty-Second Annual IEEE Symposium on Logic in Computer Science (LICS 2007), IEEE Computer Society Press, July 2007, pp. 213–222.CrossRefGoogle Scholar
Immerman, Neil, Nondeterministic space is closed under complementation. SIAM Journal on Compututing, vol. 17 (1988), no. 5, pp. 935–938.CrossRefGoogle Scholar
Jeavons, Peter, On the algebraic structure of combinatorial problems. Theoretical Computer Science, vol. 200 (1998), no. 12, pp. 185–204.CrossRefGoogle Scholar
Jeavons, Peter, Cohen, David, and Gyssens, Marc, Closure properties of constraints. Journal of ACM, vol. 44 (1997), no. 4, pp. 527–548.CrossRefGoogle Scholar
Kiss, Emil and Valeriote, Matthew, On tractability and congruence distributivity. Logical Methods in Computer Science, vol. 3 (2007), no. 2, pp. 2:6, 20 pp. (electronic).Google Scholar
Kun, Gábor and Szegedy, Mario, A new line of attack on the dichotomy conjecture, Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC ’09, ACM, 2009, pp. 725–734.CrossRefGoogle Scholar
Ladner, Richard E., On the structure of polynomial time reducibility. Journal of ACM, vol. 22 (1975), pp. 155–171.CrossRefGoogle Scholar
Larose, Benoît and Tesson, Pascal, Universal algebra and hardness results for constraint satisfaction problems. Theoretical Computer Science, vol. 410 (2009), pp. 1629–1647.CrossRefGoogle Scholar
Larose, Benoit and Zádori, László, Bounded width problems and algebras. Algebra Universalis, vol. 56 (2007), no. 3–4, pp. 439–466.CrossRefGoogle Scholar
Madelaine, F. and Martin, B., A tetrachotomy for positive first-order logic without equality, 26th Annual IEEE Symposium on Logic in Computer Science (LICS), 2011, pp. 311–320.Google Scholar
Maróti, Miklós and McKenzie, Ralph, Existence theorems for weakly symmetric operations. Algebra Universalis, vol. 59 (2008), no. 3–4, pp. 463–489.CrossRefGoogle Scholar
Papadimitriou, Christos H., Computational Complexity, Addison-Wesley Publishing Company, Reading, MA, 1994.Google Scholar
Raghavendra, Prasad, Optimal algorithms and inapproximability results for every CSP?, STOC’08, 2008, pp. 245–254.Google Scholar
Reingold, Omer, Undirected connectivity in log-space. Journal of ACM, vol. 55 (2008), no. 4, pp. 17:1–17:24.CrossRefGoogle Scholar
Rossi, Francesca, Beek, Peter van, and Walsh, Toby, Handbook of Constraint Programming (Foundations of Artificial Intelligence), Elsevier, New York, NY, USA, 2006.Google Scholar
Schaefer, Thomas J., The complexity of satisfiability problems, Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, California, 1978), ACM, New York, 1978, pp. 216–226.Google Scholar
Siggers, Mark H., A strong malcev condition for locally finite varieties omitting the unary type. Algebra Universalis, vol. 64 (2010), no. 1–2, pp. 15–20 (English).CrossRefGoogle Scholar
Szelepcsényi, R., The method of forced enumeration for nondeterministic automata. Acta Informatica, vol. 26 (1988), no. 3, pp. 279–284.CrossRefGoogle Scholar
Taylor, Walter, Varieties obeying homotopy laws. Canadian Journal of Mathematics, vol. 29 (1977), no. 3, pp. 498–527.CrossRefGoogle Scholar
Živný, Stanislav, The Complexity of Valued Constraint Satisfaction Problems, Cognitive Technologies, Springer, Heidelberg, 2012.CrossRefGoogle Scholar