计数约束满足问题的复杂度二分

作者：Andrei Bulatov ..

论文：The Complexity of the Counting Constraint Satisfaction Problem，在 2013 年发表于 J. ACM ...

机构： Simon Fraser University ...

详情页： The Gödel Prize 2021

约束满足问题（CSP）

CSP 问题是典型的决策问题，包括 SAT、SMT、MIP 等，通常具有较高的复杂度。

定义：约束满足问题（的一个实例）是一个三元组P＝(V，D，C)，其中

• V是一个有限的变量集合，

• D 是一个（元素）有限的值域，

• C 是有限的约束集，其中每个约束表示为 C＝(x，R)，其中 x 是长度为 n 的变量元组，称为 C 的 scope， R 是 D 上的 n 元关系（relation），称为 C 的约束关系。

赋值是一个映射f：V → D，如果 f(x)∈R，则满足约束 C＝(x，R)。如果赋值 f 满足所有约束，那么它称为解（solution）。

关于 CSP 的三个基本问题是

• 满足性（satisfiability）：即解的存在性；

• 优化（optimization）：如果解不存在，那么满足最多约束的赋值是什么？

• 计数（counting）：存在多少解？

实例：3-SAT 问题是一个标准的 NP-complete 问题，3-SAT 是指一些 clause 的合取范式，其中每个 clause 恰好包含 3 个 literal。例如

φ＝(x₁∨¬x₂∨x₃)∧(¬x₄∨x₅∨¬x₁)∧(¬x₁∨¬x₄∨¬x₃)

是 3-SAT 问题的一个实例，它对应

• V＝{x₁，. . .，x₅}；

• D＝{0，1}；

• C 作为对 φ 中约束关系的描述。

如果将D 上的约束关系集合记为语言 D，那么这个问题可简记为 CSP(D)。

CSP 复杂度二分猜想

Feder 与 Vardi 在 1998 年提出关于 CSP 的复杂度二分猜想：对于任意有限域上的约束语言D，问题 CSP(D) 要么是 P 难度，要么是 NP-complete 难度。

注意，如果 P≠ NP，那么它们之间会有很多复杂度层级，所以这个二分不是平凡的。当时这个猜想来自两个结果：

• 二元域上所有语言的 CSP 复杂度是二分的（Schaefer，1978 年）；

• 如果约束语言仅由二元对称关系组成，那么其上的 CSP 复杂度也是二分的（Hell and Nesetril，1990 年）。

到 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) 在多项式时间内可解。

这是有限域上证明 CSP 问题复杂度二分的初步思路。从满足性 CSP 到计数 CSP 没有本质的难度，但难度在于具体如何为任意问题的约束语言找到与 3-SAT 问题的对应（如果存在）。Bulatov 的论文中包含了更多实在难以理解的技术细节。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。