计数约束满足问题的复杂度二分 (3-2)

到 2013 年 Bulatov 才完全证明有限域上一般关系的结果，事实说明从二元域和二元对称关系到有限域和一般关系的扩展并不是容易的。

Primitive Positive Definability

主要方向是寻找对不同难度的约束语言更精细的描述方式。我们知道如果一个计算问题 A 能在某种意义上模拟 B，那么 A 至少有 B 的难度。在 Bulatov 的证明中，起到相似作用的是 primitive positive definabiligy，或 pp-definability。这一概念来自 universal algebra（通用代数）。

在 CSP 背景下，如果D 和 ε 是两个相同域上的约束语言， D pp-defines ε 是说 ε 中的每个关系都能由：D 中的（约束）关系，相等关系，合取，存在量词构成的一阶公式定义。pp-definability 带来了 CSP 问题的一种规约结果：如果 D pp-defines ε，那么 CSP(ε) 能规约到 CSP(D)。

可以用一个例子说明这种规约。如果R 是值域 D 上的任意三元关系，考虑 CSP(ε) 包含以下两个关系：

S(x，y) iff∃z，R(x，y，z)∧R(y，y，x)， T(x，y) iff R(x，x，x)∧(x＝y).

可以发现关系S 与 T 是由 pp-formula 定义，因此约束语言 D＝{R} pp-defines 约束语言 ε＝{S，T}。如果我们考虑这样一个实例

S(x₃，x₂)，T(x₁，x₄)，S(x₂，x₄) .

S 与 T 能由它们的 pp-definition 定义，不过需要引入一些新的变量。这得到 CSP(D) 的一个实例：

R(x₃，x₂，y₁)，R(x₂，x₂，x₃)；R(x₁，x₁，y₁)，x₁＝x₄；R(x₂，x₄，x₂)，R(x₄，x₄，x₂).

显然CSP(D) 有解当且仅当原本的 CSP(ε) 有解。

pp-definablity 提供了比较相同域上不同语言的 CSP 问题复杂度的一种更有力方法（相对于传统的规约），它更进一步的概念是 pp-interpretability。这样可以得到一列偏序集，它排列了 CSP 问题的复杂度。

幂等约束语言

下一步是在 pp-interpretability 定义的复杂度偏序集上找一个好的基准（参照点）。这个基准是幂等（idempotent）约束语言。

幂等约束语言是指至少包含了D 上所有一元关系的语言。对于 CSP 问题，有限域上的一元关系足够简单，以至于不影响除此之外剩下的约束语言的复杂度。因此有下述的易处理猜想（tractability conjecture）：

如果一个幂等约束语言D 不能 pp-interpret 3-SAT 约束语言，那么 CSP(D) 在多项式时间内可解。

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。