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

刘莹 等: 正则图上对称双态自旋系统相关的细密度二分定理 4529

上的一个 signature grid. 限制下的问题是一个二部图 Holant 问题, 记作 Holant q (H|G).

当上下文语义清晰时, 常将 Ω(G,π) 中 π 的信息隐藏进 G 中, 用 G 指代 Ω. 若函数集 F = {F} 只包含一个函数,
F 表示 . 常用前缀
则直接用 F pl-表示平面限制, 如 pl-Holant(F) 表示平面 Holant(F) 问题.
S
根据一个相互作用函数为 g 的双态自旋系统 , 可以构造一个 signature grid Ω(G,π), 其中 G 为一个二部图
,
(V L ∪V R ,E) V L = V(S) 内每个点表示一个粒子, 被 π 映射到一个布尔相等函数; V R 内每个点对应 E(S) 内的一条边,
被 π 映射到 g; 若 u ∈ V R 对应 E(S) 内边 (v 1 ,v 2 ), 则在 E 中加入边 (u,v 1 ) 和 (u,v 2 ). 根据定义, S 的配分函数的值恰好
等于 #(Ω). 反之亦然, 故该系统的配分函数计算问题, 多项式时间等价于 Holant(EQ|g), 其中 EQ 包含所有的布尔
相等函数. 例如#VC ≡ poly Holant(EQ|[0, 1, 1]). 若限制自旋系统的底层图结构为 k 正则图, 其中 为正整数, 则这样
k
的问题多项式时间等价于 Holant(= k |g), 其中 = k 表示 k 元布尔相等函数.
2.3 指数时间假设
根据著名的 P , NP 假设, SAT 问题被广泛相信不能在多项式时间内求解; 类似的, 根据 P , #P 假设, #SAT 不
能在多项式时间内求解. Impagliazzo 等人 [21,22] 提出了比 P , NP 更强的假设: 指数时间假设 (exponential time
hypothesis), 等价定义如下.
指数时间假设 (ETH): 总存在一个大于 0 的常数 ε, 使得 3-SAT 问题没有 2 εN 时间的确定性算法, 其中 N 表示
输入 3-CNF 公式的变量个数.
Dell 等人 [24] 将 ETH 发展到了计数版本#ETH 和随机版本 rETH, 这两个假设定义如下.
计数指数时间假设 (#ETH): 总存在一个大于 0 的常数 ε, 使得#3-SAT 问题没有 2 εN 时间的确定性算法, 其中
N 表示输入 3-CNF 公式的变量个数.
随机指数时间假设 (rETH): 总存在一个大于 0 的常数 ε, 使得 3-SAT 问题没有错误率低于 1/3 的 2 εN 时间内的
N 表示输入 3-CNF 公式的变量个数.
近似算法, 其中
利用 Impagliazzo 等人证明的稀疏化引理 [22] , 以上假设可以加强到没有 2 εM 的确定性或者近似算法, 其中 M
表示输入 3-CNF 公式的子句个数. 从定义可以看出, rETH 暗示了 ETH, 而 ETH 暗示了#ETH, 反方向未知. 这 3 个
假设可按照 rETH, ETH, #ETH 顺序排列, 前一个假设不弱于后一个 (普遍认为前一个强于后一个).
根据#ETH, #3-SAT 的复杂性下界为 2 Ω(N) (或 2 Ω(M) ). 在以往复杂性下界证明中, 人们常常建立一个已知困难问
题到目标问题的多项式时间归约, 来传递#P 难或#P 完全性质; 当传递的复杂性下界从多项式时间变为 2 Ω(N) 时间
时, 所建立的归约类型与多项式时间归约不同. 由于本文涉及的问题都具有图形化实例, 因此本小节仅介绍图上问
题之间的归约定义.
多项式时间归约 ( ⩽ poly ): A 和 B 是两个图上的问题. 给定 A 的一个规模为 n 的输入图 G A , 总存在一个算法 T
满足以下条件, 则称 A 可以多项式时间归约到 B, 记作 A ⩽ poly B.
(1) T 构造了多个 B 的实例 G 1 ,G 2 ,...,G p 去访问 B 的神谕;
(2) 根据 B(G 1 ),B(G 2 ),...,B(G p ), T 计算得到 A(G) 且总消耗时间为 poly(n).
若 A ⩽ poly B 且 B ⩽ poly A, 则称 A 和 B 多项式时间归约等价, 记作 A ≡ poly B.
亚指数时间归约 ( ⩽ serf ): A 和 B 是两个图上的问题. 给定 A 的一个规模为 n 的输入图 G A 和一个时间运行参数
ε > 0, 总存在一个算法 T 满足以下条件, 则称 A 可以亚指数时间归约到 B, 记作 A ⩽ serf B.
(1) T 构造了多个 B 的实例 G 1 ,G 2 ,...,G p 去访问 B 的神谕, 且每个新生成实例的规模是 O(n);
εn
(2) 根据 B(G 1 ),B(G 2 ),...,B(G p ), T 计算得到 A(G) 且总消耗时间不超过 2 .
若 A ⩽ serf B 且 B ⩽ serf A, 则称 A 和 B 亚指数时间归约等价, 记作 A ≡ serf B.
与多项式时间归约相比, 亚指数时间归约放松了对归约时间的限制, 但要求新生成实例的规模与原实例的规
模保持线性关系. 图的规模即为图的表达长度, 一般用图的点数或者边数指代. 在本文中, 如无特殊说明, 图的规模
即为图的点数.
引理 1. A 和 B 是两个图上的问题且 A ⩽ serf B. 若存在 ε A > 0 使得, 对于 n A 个点的图 G A A(G A ) 不能在 2 ε A n A 时间
,