Implementing a Test for Tractability
Implementing a Test for Tractability
复制标题
实施易处理性测试
DOI：
10.1023/b:cons.0000024049.41091.71
复制
发表时间：
2004
期刊：
影响因子：
1.6
通讯作者：
P. Jeavons
中科院分区：
文献类型：
--
作者：
R. Gault;P. Jeavons
在约束满足理论中，确定哪些约束集是NP完全问题，哪些约束集是易处理问题是一个重要的开放问题。在以前的论文中已经表明，可以使用关系的代数性质来识别易处理性和NP完全性的某些充分条件，并且可以通过求解特定形式的约束满足问题来测试这些条件本文描述了一个程序，它可以解决有关指标问题的任意套约束的小域，并且对于较大域上的某些约束集合。该程序的主要创新之处在于它能够处理问题中存在的许多对称性;它也有能力保持对称性的情况下，这加快了解决方案。使用这个程序，我们已经系统地研究了所有个人的二元关系的复杂性在一个域的大小为四或更少，和所有单个三元关系的大小为3或更小的域。这种自动分析包括超过450000个新的NP完全性结果的推导，并精确地确定了一小部分的个人关系，不能被归类为任何听话的或NP-完全使用的代数条件在以前的论文。
The question of determining which sets of constraints give rise to NP-complete problems, and which give rise to tractable problems, is an important open problem in the theory of constraint satisfaction. It has been shown in previous papers that certain sufficient conditions for tractability and NP-completeness can be identified using algebraic properties of relations, and that these conditions can be tested by solving a particular form of constraint satisfaction problem (the so-called indicator problem).This paper describes a program which can solve the relevant indicator problems for arbitrary sets of constraints over small domains, and for some sets of constraints over larger domains. The main innovation in the program is its ability to deal with the many symmetries present in the problem; it also has the ability to preserve symmetries in cases where this speeds up the solution.Using this program, we have systematically investigated the complexity of all individual binary relations over a domain of size four or less, and of all individual ternary relations over a domain of size three or less. This automated analysis includes the derivation of more than 450 000 new NP-completeness results, and precisely identifies the small set of individual relations which cannot be classified as either tractable or NP-complete using the algebraic conditions presented in previous papers.