Skip to main content

Research Repository

Advanced Search

The complexity of maximal constraint languages

Bulatov, A.; Krokhin, A.; Jeavons, P.

Authors

A. Bulatov

P. Jeavons



Abstract

Many combinatorial search problems can be expressed as “constraint satisfaction problems” using an appropriate “constraint language”, that is, a set of relations over some fixed finite set of values. It is well-known that there is a trade-off between the expressive power of a constraint language and the complexity of the problems it can express. In the present paper we systematically study the complexity of all maximal constraint languages, that is, languages whose expressive power is just weaker than that of the language of all constraints. Using the algebraic invariance properties of constraints, we exhibit a strong necessary condition for tractability of such a constraint language. Moreover, we show that, at least for small sets of values, this condition is also sufficient.

Citation

Bulatov, A., Krokhin, A., & Jeavons, P. (2001). The complexity of maximal constraint languages. In Proceedings of the 33rd annual ACM symposium on theory of computing (667-674). https://doi.org/10.1145/380752.380868

Conference Name 33rd ACM Symposium on the Theory of Computing(STOC)
Conference Location Crete, Greece
Publication Date Jan 1, 2001
Deposit Date Mar 29, 2010
Publisher Association for Computing Machinery (ACM)
Pages 667-674
Series Title Annual ACM symposium on theory of computing
Series Number STOC '01
Book Title Proceedings of the 33rd annual ACM symposium on theory of computing.
DOI https://doi.org/10.1145/380752.380868
Additional Information July 6-8, 2001


You might also like



Downloadable Citations