The complexity of maximal constraint languages
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 con...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2001
|
| _version_ | 1797050229531344896 |
|---|---|
| author | Bulatov, A Krokhin, A Jeavons, P |
| author_facet | Bulatov, A Krokhin, A Jeavons, P |
| author_sort | Bulatov, A |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T18:02:05Z |
| format | Journal article |
| id | oxford-uuid:001f26b9-4375-4b5c-8153-4db108be106e |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T18:02:05Z |
| publishDate | 2001 |
| record_format | dspace |
| spelling | oxford-uuid:001f26b9-4375-4b5c-8153-4db108be106e2022-03-26T08:27:54ZThe complexity of maximal constraint languagesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:001f26b9-4375-4b5c-8153-4db108be106eEnglishSymplectic Elements at Oxford2001Bulatov, AKrokhin, AJeavons, PMany 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. |
| spellingShingle | Bulatov, A Krokhin, A Jeavons, P The complexity of maximal constraint languages |
| title | The complexity of maximal constraint languages |
| title_full | The complexity of maximal constraint languages |
| title_fullStr | The complexity of maximal constraint languages |
| title_full_unstemmed | The complexity of maximal constraint languages |
| title_short | The complexity of maximal constraint languages |
| title_sort | complexity of maximal constraint languages |
| work_keys_str_mv | AT bulatova thecomplexityofmaximalconstraintlanguages AT krokhina thecomplexityofmaximalconstraintlanguages AT jeavonsp thecomplexityofmaximalconstraintlanguages AT bulatova complexityofmaximalconstraintlanguages AT krokhina complexityofmaximalconstraintlanguages AT jeavonsp complexityofmaximalconstraintlanguages |