Page 131 - 《软件学报》2025年第10期

4528 软件学报 2025 年第 36 卷第 10 期

⊗k
X = X ⊗(k−1) ⊗ X. 一个 k 元函数 F 是退化的, 当且仅当它可以写作一些一元函数的张量积, 即 F = U 1 ⊗U 2 ⊗...⊗U k
U 1 ,...,U k 成立.
对某些一元函数
e
一个无向图 G 可以用元组 (V,E) 表示, 其中 V 表示顶点集, E 表示边集. V,E 也记作 V(G),E(G). 一条边 的两
v
v
l
e
v
个端点若为同一点 v, 则称 为点 的一条自环边; 若存在 条边有相同的两端点 和 u, 则将这些边视为 和 u 之
v
u
间的一条 l 重边. 若图 G 中没有自环和重边, 则 G 为简单图, 并常用元组 (u,v) 来指代 G 中两端点为 和 的边.
v
v
v
N(v) 和 E(v) 分别表示点 的邻点和邻边集合; d(v) 表示点 的度数, 即点 的邻边条数, 其中自环计 2 条, l 重边计
V R , 且
l 条. 图 G 的最大度记作 ∆ = max{ d(v)|v ∈ V} . 若 G 是二部图, 则 V 可以分割成两个不相交的非空点集 V L 和
G 中任一边的一端点在 V L 中且另一端点在 V R 中. 二部图也常用元组 (V L ∪V R ,E) 表示, 其中 V L 和 V R 中的点常分别
k
称为“左侧”和“右侧”的点. 若 G 是一个简单图且任意点的度数都为某个正整数 k, 则称 G 为 正则图. 若 G 能按照
任意两条边不在非端点处相交的方式画在平面上, 则称 G 为平面图, 且符合要求的画法称为 G 的一个平面
嵌入.
下面介绍两个典型的图上的#P 完全问题.
点覆盖集数目问题 (#VC): 给定一个图 G(V,E), 一个点子集 S ∈ V 被称作 G 的一个点覆盖集 (vertex cover) 当
且仅当, ∀e ∈ E e , 至少有一端点在 S 内. 点覆盖集数目问题, 简记为#VC, 即为求给定图的点覆盖集数目.
布尔满足性数目问题 (#SAT): 给定一个正整数 k, 一个定义在 n 个布尔变量 x 1 , x 2 ,..., x n 上的公式 ϕ 被称为 k
合取范式, 记作 k-CNF, 当且仅当 ϕ 可以写作 m 个子句的合取, 即 ϕ = ∧ i∈[m] C i , 其中 m 为某个正整数, C i 表示第 个
i
.
i
j
子句且形如 ∨ j∈[k] l i,j l i,j 表示第 个子句中的第 个文字, 且 l i,j 对应某个布尔变量 x ∈ {x 1 , x 2 ,..., x n } 或者某个变量的
否 ¯ x = 1− x. 一组布尔赋值 a = (a 1 ,...,a n ) 满足 ϕ(a) = 1, 则称其为 ϕ 的一组满足性赋值. 给定一个 k-CNF 公式 ϕ,
ϕ 是否有满足性赋值称为布尔满足性问题, 简记为 ϕ 的满足性赋值的组数, 被称为布尔满足性赋数
判定 k-SAT; 求
目问题, 简记为#k-SAT. SAT={k-SAT | k ∈ N} 且#SAT={#k-SAT | k ∈ N}.
2.2 Holant 问题
在第 1 节中, 本文介绍了双态自旋系统模型. 若这样的一个自旋系统 S(V,E) 内相互作用函数为 g = [0,1,1], 即
∏
要求 S 内每条边至少有一端点变量赋值为 1. 给定一组点赋值, 若其满足 g(σ(u),σ(v)) = 1 , 则此时对应赋值 1
(u,v)∈E
的点构成的集合恰好是 S 的一个点覆盖集; 反之亦然. 故该自旋系统的配分函数的值恰好是图 S 的点覆盖集数目.
由此可知, #VC 问题多项式时间等价于相互作用函数为 [0,1,1] 的双态自旋系统的配分函数计算问题. 与#VC 不同
的是, #k-SAT 问题的实例并不总能被表达成一个自旋系统.
Holant 是更一般的计数问题模型. Holant 值概念 [31] 由 Valiant 提出, 并被 Cai 等人 [32] 发展成 Holant 问题模型.
令 q 是一个大于等于 2 的正整数, F 是一个定义在 [q] 上的函数组成的集合. F 上的一个 signature grid 是一个元组
Ω(G,π), 其中 G 是一个点集为 V 且边集为 E 的图; π 是一个将 F 内某个函数映射到 G 内某个点的函数. 以 F 为参
数函数集的 Holant 问题, 记为 Holant q (F), 定义如下.

Holant q (F) 问题: 接受 F 上的一个 signature grid Ω(G,π) 为输入, 并输出

∑ ∏
# q (Ω) = F v (σ| E(v) ),
σ:E→[q] v∈V
v
v
其中, σ 表示对所有边的一组布尔赋值; σ| E(v) 表示 σ 下点 的邻边 E(v) 的赋值; F v 是被 π 映射到点 的函数, 其值
由 σ| E(v) 按照一定顺序决定 (该顺序已被 π 确定).
λF v λ 为某个非 0 λ 倍; 这种简单的倍数关系是容易计算及
,
若将 F v 替换成 常数, 根据定义, 实例的值仅变化
相互归约转换的, 故在 Holant 问题中, 对任意函数 F 和非 0 常数 , λF 被视为等价的, 它们之间的相互转化被
λ F 和
称为归一化 (normalization).
,
;
当 q = 2 时, F 被限定在布尔定义域 {0,1} Holant 2 (F) 是一个布尔 Holant 问题, 简记为 Holant(F) # 2 (Ω) 也简
记为 #(Ω). 若 F 能被划分成不相交的两个函数集合 H 和 , 且限制输入的 Ω(G,π) 中 G 为一个二部图 (V L ∪V R ,E),
G
其中 V L 的每个点被 π 映射到 H 内的某个函数, V R 的每个点被 π 映射到 G 内的某个函数. 这样的 Ω 也被称为 H|G