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

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

总有上述某一条归约链证明了其对于某个正数 ε 没有 2 εN 时间的确定性算法. 故定理 1 得证.
4.2 平面图

Holant(g|= k ) 问题限制到平面图时, 该问题的细密度复杂性.
接下来考虑
若存在 {g|= k } 门能实现一个四元布尔函数 Cr(x 1 ,y 1 , x 2 ,y 2 ), 该函数仅在 x 1 = x 2 且y 1 = y 2 时取值为 1, 其余情况取
值为 0, 则对于 Holant(g|= k ) 的任意实例 G, 利用 Cr 替换其内部的交叉结构, 可以构建一个 Holant(g|= k ) 的平面图实
′ ′ pl-Holant(g|= k ) 的多项式时间归约. Holant(g|= k ) 的实例,
例 G , 有 #(G ) = #(G). 这样就构建了 Holant(g|= k ) 到 G 为
2 2 ′ 2 O(|V(G)|)
有 |E(G)| = O(|V(G)|), 故 G 中交叉数量为 O(|E(G)| ) = O(|V(G)| ); 则 G 的点数为 O(|V(G)| ). 若 #(G) 不能在 2
√
′ 2 O( |V(G ′ )|) 时间内计算. 此情况下, 容易将一般图上问题的细密度复杂性下界
时间内计算, 容易证明 #(G ) 定不能在
发展到平面图上对应问题的细密度复杂性下界. 遗憾的是, 很多情况下 {g|= k } 门不能直接实现 Cr, 需要借助一些一
pl-Holant({[0,1,1],[1,−1]}|= 3 ) 的细密度复杂性下界 (定理 Cr.
元函数, 如 6) 证明就依赖于 [1,−1] 帮助构造
pl-Holant({[0,1,1],[1,−1]}|= 3 ) 问题作一个简单的扩展.
先对
√
引理 5. k 是不小于 3 的整数. 若#ETH 成立, 则存在 ε > 0 使得 pl-Holant({[0,1,1],[1,−1]}|= k ) 不能在 2 ε N 时间
N 表示输入图的点数. 若 rETH 成立, 即使限制输入实例的值非 0 即 1, 该下界仍成立.
内计算, 其中
证明: 令 G 为 pl-Holant({[0,1,1],[1,−1]}|= 3 ) 的一个实例. 不妨设 |V(G)| = n.
若 k 为奇数, 利用 (= k ) 与 (k −3) 个 [1,−1] 相连则可得到右侧的 (= 3 ) 函数, 将 G 中的 (= 3 ) 函数替换成这样的等
′ ′
价构件, 则构造了 pl-Holant({[0,1,1],[1,−1]}|= k ) 的实例 G , 有 #(G ) = #(G).
k 为偶数, 则利用图 (= k ) 相连则可得
若 3(a) 所示构件可以实现左侧 [−1,−1]; 再利用 (k −3) 个 [−1,−1] 与
到右侧的 [−1,0,0,−1] 函数. 若 G 中有偶数个 (= 3 ) 函数, 将每个 (= 3 ) 替换成 [−1,0,0,−1] 相应构件, 则构造了 pl-Holant
G
′
′
({[0,1,1],[1,−1]}|= k ) 的实例 , 且 #(G ) = #(G) . 若 G 中有奇数个 (= 3 ) 函数, 则将每个 (= 3 ) 替换成 [−1,0,0,−1]
′′
′ ′ ′ G , 该连通分支是一个
相应构件, 得到的实例 G 满足 #(G ) = −#(G). 在 G 中额外加入一个连通分支构造新的实例
(= k ) 与 1 个 [−1,0] 和 (k −1) 个 [1,−1] 相连, 其中左侧的 [−1,0] 由图 3(b) 所示构件实现. 新增加的这一连通分支带
′′ ′ ′ ′′
来一个 −1 因子, 故 #(G ) = −#(G ) = #(G). 重命名 G = G .

[0, 1, 1] [1, −1]
[0, 1, 1] =k [0, 1, 1] =k
[0, 1, 1] [1, −1]
[1, −1]
(a) 实现 [−1, −1] (b) 实现 [−1, 0]
k 为大于 3 的偶数
图 3 两个 {[0,1,1],[1,−1]|= k } 门, 其中

′ ′ ′
通过以上方式, 总能在 poly(n) 内构造出 G , 有 #(G ) = #(G). 假设 |V(G )| = N, 有 N = O(n).
√
′
′ 2 ε N G ,
假设引理不成立, 则对任意 ε > 0, 使得 #(G ) 能在 时间内计算. 那么任给一个 G, 通过上述方式构造出
√ √
′
从而计算 #(G ) = #(G), 整个算法的总时间为: 2 ε N +poly(n) ⩽ 2 εc n , 其中 c 为某个常数. 在 n 足够大时, 对于任意时
√
ε
′ εc n ε ′ √ n #(G), 这与定理 矛盾, 故引理
间运行参数 ε > 0, 总可以选择足够小的 , 使得 2 ⩽ 2 时间内能计算出 6
成立.
√ √
由上述证明可以看到, 在平面图问题之间传递 2 Ω( N) 时间下界, 需要构造 2 O( N) 时间的归约, 同时归约过程中
产生的新实例的规模要求仅线性变化. 这样的归约简称为根号亚指数时间归约. 可以看到, 常数规模的构件构造和
全息变换仍然适用, 但多项式时间插值和块插值均已失效; 因此, 探索平面图上 Holant(g|= k ) 问题的细密度二分定
理, 需要新的归约思路和归约方法, 以建立根号亚指数时间归约.
参考定理 1 的证明, 假设 F 和 H 是两个布尔函数集, 建立 Holant(F) 到 Holant(H) 的归约, 本质是以直接 (构
件构造和全息变换) 或间接 (插值) 的方式, 利用 H 内的函数实现 F 内所有函数. 因此, F 内包含的函越容易被实