Distance constraint satisfaction problems
Distance constraint satisfaction problems
复制标题
距离约束满足问题
DOI：
10.1016/j.ic.2015.11.010
复制
发表时间：
2016
影响因子：
1
通讯作者：
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.
登录
查看更多内容
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
M. Maróti;R. McKenzie
通讯作者：
R. McKenzie
影响因子：
1.6
作者：
Feder, T;Vardi, MY
通讯作者：
Vardi, MY
DOI：
10.2168/lmcs-3(1:2)2007
发表时间：
2006
期刊：
Log. Methods Comput. Sci.
影响因子：
--
作者：
M. Bodirsky
通讯作者：
M. Bodirsky
CSP 代数方法的最新结果
DOI：
10.1007/978-3-540-92800-3_4
发表时间：
2008
期刊：
2009 50th Annual IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
A. Bulatov;M. Valeriote
通讯作者：
M. Valeriote
将平等还原为原始积极的可相互定义性
DOI：
10.2178/jsl/1286198146
发表时间：
2008
期刊：
The Journal of Symbolic Logic
影响因子：
--
作者：
M. Bodirsky;Hubie Chen;M. Pinsker
通讯作者：
M. Pinsker