Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.


Durham Research Online
You are in:

The complexity of maximal constraint languages.

Bulatov, A. and Krokhin, A. and Jeavons, P. (2001) 'The complexity of maximal constraint languages.', in Proceedings of the 33rd annual ACM symposium on theory of computing. New York: Association for Computing Machinery, pp. 667-674. Annual ACM symposium on theory of computing. (STOC '01).

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.

Item Type:Book chapter
Additional Information:33rd Annual ACM Symposium on Theory of Computing, 6-8 July, 2001, Crete-Greece.
Full text:Full text not available from this repository.
Publisher Web site:http://dx.doi.org/10.1145/380752.380868
Record Created:29 Mar 2010 15:05
Last Modified:08 Nov 2010 12:32

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library