A finer reduction of constraint problems to digraphs
A finer reduction of constraint problems to digraphs
复制标题
将约束问题更好地简化为有向图
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
T. Niven
中科院分区：
文献类型：
--
作者：
Jakub Bulín;D. Delic;M. Jackson;T. Niven
众所周知，对一般关系结构A上的约束满意度问题是多项式时间等于某些相关的图片上的约束问题。我们提出了这种结构的一种变体，并表明相应的约束满意度问题是与A上的logspace相等的。此外，我们表明几乎所有常见的多态性属性都等同于A和构造的Digraph。结果，代数CSP二分法以及在Logspace和非确定性logspace中可求解的CSP的猜想等同于限制对Digraphs的限制。
It is well known that the constraint satisfaction problem over a general relational structure A is polynomial time equivalent to the constraint problem over some associated digraph. We present a variant of this construction and show that the corresponding constraint satisfaction problem is logspace equivalent to that over A. Moreover, we show that almost all of the commonly encountered polymorphism properties are held equivalently on the A and the constructed digraph. As a consequence, the Algebraic CSP dichotomy conjecture as well as the conjectures characterizing CSPs solvable in logspace and in nondeterministic logspace are equivalent to their restriction to digraphs.
DOI：
10.1137/100811258
发表时间：
2010-03
期刊：
SIAM J. Comput.
影响因子：
--
作者：
M. Dyer;David Richerby
通讯作者：
M. Dyer;David Richerby
影响因子：
1.6
作者：
Cohen D
通讯作者：
Cohen D
通用价值 CSP 的复杂性
DOI：
10.1109/focs.2015.80
发表时间：
2015
期刊：
--
影响因子：
--
作者：
Kolmogorov V
通讯作者：
Kolmogorov V