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

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

现 (例如个数越少、形式越简单), 构造归约的难度就越低. 如定理 1 的证明就选择了 Holant([0,1,1]|= 3 ) 问题为归
√
约起始. 遗憾的是, 在#ETH 假设下, pl-Holant([0,1,1]|= 3 ) 问题是否有 2 Ω( N) 时间下界还未可知, 本文只能够退一步
选择 pl-Holant({[0,1,1],[1,−1]}|= 3 ) 问题为归约起始来探讨平面 Holant(g|= k ) 的复杂性. 这就带来了一个新的归约思
路: 利用更强的假设, ETH 或 rETH, 探寻参数函数集更容易被实现的平面 Holant 问题, 以其为归约起始来降低归
约构造的难度, 从而避开插值的使用. 第 4.2.1 节利用了此思路, 虽然没有直接找到参数函数集比 {[0,1,1],[1,−1]|= k }
更简单的平面 Holant 问题, 但根据定理 6, 在 rETH 假设下, pl-Holant({[0,1,1],[1,−1]}|= 3 ) 问题在限制实例的值非
√
0 即 1 时, 仍有 2 Ω( N) 时间下界. 这意味着, 对于任意正整数 p, 在 mod p 的环境下, 只需实现与 {[0,1,1],[1,−1]|= 3 }
在 mod p 意义下等价的函数即可, 而不需要严格实现 {[0,1,1],[1,−1]|= 3 }. 这就降低了归约难度, 使得插值技术能被
规避.
4.2.1 rETH 假设下规避插值
以引理 4 的证明为例, 不妨设 H = {[1,a]} a ∈ Z). 在 mod p p 为正整数) 的环境中, 若使用多项式时间插值, 根
(
(
据费马小定理, 建立的 n 次一元多项式会被降元到 p−2 次多项式, 仅需构造 p−1 个新的实例, 即只需构造出 p−1
个形如 [1, x] 的两两线性无关函数, 来进一步恢复出该多项式的系数. 在 mod p 的环境中, 形如 [1, x] 的两两线性无
关函数总共只有 p 个, 这就意味着在进行多项式时间插值时, [1,a] 以接近 1 的概率已经被某个构件直接构造出来,
可以直接利用该构件来建立归约, 而无需进行插值. Guo 等人 [33] 在研究模 p 约束求解数目问题时, 提出了这一观
察, 并论证了在 mod p 的环境中, 对于可表达为非退化矩阵的二元函数 A, 总能利用常数规模构件实现二元函数
−1
A . 令 Z p = { x mod p|x ∈ Z}.
引理 6 [33] . p 为正整数. 对任意非退化 2×2 矩阵 A ∈ Z p , 总存在正整数 k, 使得 A mod p = A −1 mod p.
k
c = a/b. 根据费马小定
任何一个有理数都可以表示为两个整数之商, 即对任意 c ∈ Q, 存在 a,b ∈ Z 且 b , 0, 有
理, 对任意与 b 互素的质数 , p−2 mod p. 若 a,b 均与 p 互素, 则称 与 p 互素.
c
p c mod p = ab
推论 1. A ∈ Q 为 2×2 矩阵, 将其每一项写成分数形式, p 是与每项分母互素的质数. 若 A mod p 非退化, 则总
k
−1
存在正整数 k, 有 A mod p = A mod p.
想规避掉插值, 则需要寻找一个合适的归约起始问题, 该问题对于某个正整数 p, 在 mod p 的环境中仍有
√
2 Ω( N) 时间下界. 根据定理 6, 在 rETH 假设下, 限制 pl-Holant({[0,1,1],[1,−1]}|= k ) 实例的值非 0 即 1, 问题依然有
√
2 Ω( N) 时间复杂性下界. 这恰好为取模运算的使用提供了便利. 换而言之, 要证明一个平面计数问题 B 在 rETH 假
设下的细密度下界, 只需建立受限 pl-Holant({[0,1,1],[1,−1]}|= k ) 到 B 的归约: 对于 pl-Holant({[0,1,1],[1,−1]}|= k ) 的
任一值非 0 即 1 的实例 G, 构造出 B 的一个实例 G , 选取一个合适的指数 , 使得 #(G ) mod p , 0 则 #(G) = 1,
p
′
′
√
′
′ #(G) = 0; 并保证归约时间为 2 O( |V(G)|) |V(G )| = O(|V(G)|) 即可.
#(G ) mod p = 0 则 时间且
根据定理 2, 若函数 g = [a,1,b] a,b ∈ Q ) 满足 (1) a = b = 0 , 或 (2) ab = 1 , 或 (3) ab = −1 且 a = b (即
2k
2k
(
(a,b) ∈ {(1,−1),(−1,1)}), 则对于任意正整数 k ⩾ 3, 平面 Holant({g,[0,1]}|= k ) 有多项式时间算法; 否则, 若 rETH 成立,
√
ε N
则存在 ε > 0, 使得该问题不能在 2 时间内计算, 其中 N 表示输入图的点数.
条件被满足时, 根据定理 7, 多项式时间算法已被 Cai 等人 [17,19,20] 给出; 只需考虑证明定理 2 的难解性. 本节包
含的证明中, ≡ ( mod p) 符号简写为 =.
√
引理 7. 若 rETH 成立, 对于任意 b ∈ Q−{0} 和任意正整数 k ⩾ 3, 存在 ε > 0, 使得 Holant([0,1,b]|= k ) 不能在 2 ε N
时间内计算, 其中 N 表示输入图的点数.
证明: 令 p 是与 b 互素的质数, 即 b mod p , 0. 利用图 4 所示 {[0,1,b]|= k } 门实现了右侧的 [0,1,b k−1 ] 函数. 又通
( )(( )( )) t
0 1 0 1 0 1
过图 5 所示的 {[0,1,b]|= k } 门, 选取满足推论 1 的 t , 可实现左侧的二元函数 =
1 b 1 b k−1 1 b
( )(( )( )) −1 ( ) −1
0 1 0 1 0 1 0 1 k−1 A, 总可
1 b 1 b k−1 1 b = 1 b k−1 = [−b ,1,0]. 由此也可看出, 对于一侧的非退化二元函数
−1
以实现另一侧二元函数 A .
将图 4 中一个 [0,1,b] 替换成 [−b k−1 ,1,0], 则可得到右侧的二元不等函数 [0,1,0]. 对任意正整数 l, 利用形如