Abstract
We classify the computational complexity of all constraint satisfaction problems where the constraint language is preserved by all permutations of the domain. A constraint language is preserved by all permutations of the domain if and only if all the relations in the language can be defined by boolean combinations of the equality relation. We call the corresponding constraint languages equality constraint languages.
For the classification result we apply the universal-algebraic approach to infinite-valued constraint satisfaction, and show that an equality constraint language is tractable if it admits a constant unary polymorphism or an injective binary polymorphism, and is NP-complete otherwise. We also discuss how to determine algorithmically whether a given constraint language is tractable.
Similar content being viewed by others
References
Allender, E., Bauland, M., Immerman, N., Schnoor, H., Vollmer, H.: The complexity of satisfiability problems: refining Schaefer’s theorem. In: Electronical Colloquium on Computational Complexity, 2004
Bodirsky, M.: Constraint satisfaction with infinite domains. PhD thesis, Humboldt-Universität zu Berlin (2004)
Bodirsky, M., Dalmau, V.: Datalog and constraint satisfaction with infinite templates. In: Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS’06). LNCS, vol. 3884, pp. 646–659. Springer, Berlin (2006). A journal version is available from the webpage of the first author, 2006
Bodirsky, M., Kára, J.: The complexity of equality constraint languages. In: Proceedings of the International Computer Science Symposium in Russia (CSR’06). LNCS, vol. 3967, pp. 114–126. Springer, Berlin (2006)
Bodirsky, M., Nešetřil, J.: Constraint satisfaction with countable homogeneous templates. J. Log. Comput. 16(3), 359–373 (2006)
Bodnarčuk, V.G., Kalužnin, L.A., Kotov, V.N., Romov, B.A.: Galois theory for post algebras, part I and II. Cybernetics 5, 243–539 (1969)
Bulatov, A., Krokhin, A., Jeavons, P.G.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34, 720–742 (2005)
Cameron, P.J.: Oligomorphic Permutation Groups. Cambridge University Press, Cambridge (1990)
Cohen, D., Jeavons, P., Jonsson, P., Koubarakis, M.: Building tractable disjunctive constraints. J. ACM 47(5), 826–853 (2000)
Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications, vol. 7 (2001)
Dechter, R., van Beek, P.: Local and global relational consistency. TCS 173(1), 283–308 (1997)
Garey, M.R., Johnson, D.S.: A Guide to NP-completeness. CSLI Press, Stanford (1978)
Geiger, D.: Closed systems of functions and predicates. Pac. J. Math. 27, 95–100 (1968)
Heindorf, L.: The maximal clones on countable sets that include all permutations. Algebra Universalis 48, 209–222 (2002)
Hodges, W.: A Shorter Model Theory. Cambridge University Press, Cambridge (1997)
Krasner, M.: Généralisation et analogues de la théorie de Galois. In: Congrés de la Victoire de l’Ass. France avancement des sciences, pp. 54–58, 1945
Nebel, B., Bürckert, H.-J.: Reasoning about temporal relations: a maximal tractable subclass of Allen’s interval algebra. J. ACM 42(1), 43–66 (1995)
Ottmann, T., Widmayer, P.: Algorithmen und Datenstrukturen. Spektrum Akademischer Verlag (2002)
Pinsker, M.: Maximal clones on uncountable sets that include all permutations. Algebra Universalis 54(2), 129–148 (2005)
Pinsker, M.: The number of unary clones containing the permutations on an infinite set. Acta Sci. Math. (Szeged) 71, 461–467 (2005)
Pinsker, M.: Maximal clones on uncountable sets that include all permutations. Algebra Universalis 54(2), 129–148 (2005)
Pöschel, R., Kalužnin, L.A.: Funktionen- und Relationenalgebren. Deutscher Verlag der Wissenschaften (1979)
Szendrei, A.: Clones in universal Algebra. Seminaire de mathematiques superieures. Les Presses de L’Universite de Montreal (1986)
Valiant, L., Vazirani, V.: NP is as easy as detecting unique solutions. In: Proc. ACM Symp. on Theory of Computing, 1985
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bodirsky, M., Kára, J. The Complexity of Equality Constraint Languages. Theory Comput Syst 43, 136–158 (2008). https://doi.org/10.1007/s00224-007-9083-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-007-9083-9