The complexity of equality constraint languages

作     者：Bodirsky, Manuel Kara, Jan 

作者机构：Humboldt Univ Algorithms & Complex Dept Berlin Germany Charles Univ Prague Fac Math & Phys Dept Appl Math Prague Czech Republic 

出 版 物：《THEORY OF COMPUTING SYSTEMS》 (计算系统理论)

年 卷 期：2008年第43卷第2期

页      面：136-158页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

主　　题：constraint satisfaction logic in computer science computational complexity clones on infinite domains 

摘      要：We classify the computational complexity of all constraint satisfaction problems where the constraint language is preserved by all permutations of the domain. A constraint language is preserved by all permutations of the domain if and only if all the relations in the language can be defined by boolean combinations of the equality relation. We call the corresponding constraint languages equality constraint languages. For the classification result we apply the universal-algebraic approach to infinite-valued constraint satisfaction, and show that an equality constraint language is tractable if it admits a constant unary polymorphism or an injective binary polymorphism, and is NP-complete otherwise. We also discuss how to determine algorithmically whether a given constraint language is tractable.