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

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

ε B > 0 使得问题 B 2 ε B n B n B 表示问题 B 输入图的点数.
内计算, 那么总存在 没有 时间的确定性算法, 其中
证明: 假设对于任意 ε B > 0, 问题 B 都有 2 ε B n B 时间内的算法. A ⩽ serf B 则存在一个带有 B 的神谕的算法 T 在
2 εn A 时间内计算 A(G A ), 其中 ε 为任意大于 0 的常数. 将 B 的神谕替换成假设的算法, 则结合 T, 可以得到一个求解
A(G A ) 的确定性算法. 假设 T 所构造的 B 的实例的点数都不超过 cn A , 其中 为某个正常数, 则确定性算法所花费
c
2 εn A ·2 ε B cn A ⩽ 2 (ε+cε B )n A 2 (ε+cε B )n A ⩽ 2 ε A n A ε B > 0
的时间不超过 . 选取足够小的 ε 和 ε B , 可以使 , 与引理中已知矛盾. 故存在
使得问题 B 没有 2 ε B n B 时间的确定性算法.
不难证明, 多项式时间归约和亚指数时间归约都具有传递性. 通过构造一系列的亚指数时间归约, 人们证明
了, 当#ETH 或 rETH 成立时, 一些计数问题的亚指数时间下界.
√
定理 4 [26] . g 是一个二元对称布尔函数且 g < {[0,1,0],[1,0,1],[a,1,b],λ[1,±i,1],λ[1,±1,−1] | ab = 1,i = −1,
λ ∈ C}. 若#ETH 成立, 则存在 ε > 0 使得 Holant({= 1 ,= 2 ,= 3 }|g) 没有 2 εn 时间的确定性算法, 其中 n 表示输入图的
点数.
定理 5 [29] . 若#ETH 成立, 则存在 ε > 0 使得 Holant(= 3 | [0, 1, 1]) 没有 2 εn 时间的确定性算法, 其中 n 表示输入图
的点数.
√
定理 6 [29] . 若#ETH 成立, 则存在 ε > 0 使得 pl-Holant(= 3 |{[0,1,1],[1,−1]}) 没有 2 ε n 时间的确定性算法, 其中 n
表示输入图的点数. 若 rETH 成立, 则该结论在限制输入实例的值非 0 即 1 的情况下仍成立.

3 归约方法

3.1 构件构造
一类最直接的归约方法称作构件构造, 即通过函数之间的相互连接实现新的函数. F 是一个定义集合 [q] 上的

函数集. 一个由 F 内函数构成的构件, 也称作 F 门, 是一个 F 上的 signature grid G(V,E ∪ X) π ( 隐含在 G 内). E 和 X
是两个不相交的边集, E 中的边两端都连接了 V 中顶点; X 中的边一端连接 V 中顶点, 另一端悬空, 也称悬挂边. G
实现了一个 |X| 元函数 Γ G , 且变量赋值为 (a 1 ,a 2 ,...,a |X| ) ∈ [q] ⊗|X| 时, 该函数取值为:

∑ ∏
Γ G (a 1 ,a 2 ,...,a |X| ) = F v ( ˆσ| E(v) ),
σ:E→[q] v∈V
其中, σ 表示 E 内边的一组赋值; ˆ σ| E(v) 表示 的邻边的 (有序) 赋值, 由 σ 和 (a 1 ,a 2 ,...,a |X| ) 共同决定. 若 X 为空, Γ G
v
为零元函数, 对应的常值即为 # q (G).
令 H 也是定义在 [q] 上的函数集. 若 G 是一个 F | H 门, 即 G 是 F | H 上的 signature grid, 且 X 的邻点全在 V L
中或 V R 中. 若 X 的邻点全在 V L 中, 则称 G 实现了一个“左侧”的函数; 相应的, 若 X 的邻点全在 V R 中, 则称 G 实现
了一个“右侧”的函数. 图 2 展示了一个实现右侧 = k 函数的 {= 2 | = 3 } 门, 其中正整数 k ⩾ 5.

=3 =2 =3 =2 =3
图 2 实现 = k 函数的 {= 2 |= 3 } 门, 包含 k −2 个 (= 3 ) 和 k −3 个 (= 2 )

假设 H 内每一个函数都可以由某个常数规模的 F 门实现. 对于 Holant q (H) 的任一实例 G, 总可以在 poly(|V(G)|)
′ ′ ′
时间内将所有点替换成对应的 F 门, 从而得到 Holant q (F) 的一个实例 G , 有 # q (G) = # q (G ) 且 |V(G )| = O(|V(G)|).
引理 2. , [q] 上的函数集, 其中 q 为大于 1 的正整数, 且 H 内每一个函数都可以由某个常数
H F 为两个定义在
规模的 F 门实现, 有:

Holant q (H)⩽ poly Holant q (F)且Holant q (H)⩽ serf Holant q (F).
3.2 全息变换
另一类归约方法被称为全息变换. 有时候, 两个表面看上去不同的计数问题实际上是不同形态下的相同问题,
全息变换就是连接它们之间的等价关系的工具.