Mathematical Foundations of Computer Science 2010
Mathematical Foundations of Computer Science 2010
复制标题
计算机科学数学基础 2010
DOI：
10.1007/978-3-642-15155-2_16
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Bodirsky M
中科院分区：
文献类型：
--
作者：
Bodirsky M
我们研究整数上模板 Γ 的约束满足问题的复杂性，其中关系可以从后继函数一阶定义。在 γ 局部有限的情况下（即 γ 的盖夫曼图具有有限度），我们证明 γ 同态等价于具有两类多态性（我们称为模最大和模最小值）之一的结构，并且 γ 的 CSP 可以在多项式时间内求解，或者 γ 同态等价于有限传递结构，或者 γ 的 CSP 是 NP 完全的。假设来自有限域约束满足的广泛相信的猜想（我们需要 Bulatov、Jevons 和 Krokhin 在传递有限模板的特殊情况下的可处理性猜想），这证明了这些 CSP 具有复杂性二分法，即要么是 P 完全的，要么是 NP 完全的。
We study the complexity of constraint satisfaction problems for templates Γ over the integers where the relations are first-order definable from the successor function. In the case that Γ is locally finite (i.e., the Gaifman graph of Γ has finite degree), we show that Γ is homomorphically equivalent to a structure with one of two classes of polymorphisms (which we call modular max and modular min) and the CSP for Γ can be solved in polynomial time, or Γ is homomorphically equivalent to a finite transitive structure, or the CSP for Γ is NP-complete. Assuming a widely believed conjecture from finite domain constraint satisfaction (we require thetractability conjectureby Bulatov, Jeavons and Krokhin in the special case oftransitivefinite templates), this proves that those CSPs have a complexity dichotomy, that is, are either in P or NP-complete.