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

作者：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 年）。

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