The complexity of maximal constraint languages
The complexity of maximal constraint languages
复制标题
最大约束语言的复杂性
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
P. Jeavons
中科院分区：
文献类型：
--
作者：
A. Bulatov;A. Krokhin;P. Jeavons
许多组合搜索问题可以用适当的“约束语言”表示为“约束满足问题”，即在某个固定的有限值集上的一组关系。众所周知，在约束语言的表达能力和它可以表达的问题的复杂性之间存在权衡。本文系统地研究了所有极大约束语言的复杂性，即其表达能力只是弱于所有约束语言的语言。利用约束的代数不变性，给出了这种约束语言可处理的一个强必要条件。此外，我们还证明了，至少对于小的值集，这个条件也是充分的。
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.