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

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

( )(( )( )) l
0 1 0 1 0 1
[0,1,b],[0,1,0],...,[0,1,b] 的路径构件, 可实现函数 = [0,1,lb]. 定存在 l 1 ,l 2 , 使得 l 1 b =
1 b 1 0 1 b
−1 和 l 2 b = 1. 故存在 {[0,1,b]|= k } 门实现左侧函数 [0,1,1] 和 [0,1,−1].
利用图 6 结构, 可以实现右侧 [0,1] 或 [0,1] . 若 k 为奇数, 利用 [0,1,1] 与 [0,1] 相连可实现左侧函数 [1,1]; 利
⊗2
G #(G) 非
用 [0,1,−1] 与 [0,1] 相连可实现左侧函数 [1,−1]. 对于 pl-Holant({[0,1,1],[1,−1]}|= k ) 的任一实例 , 0 即 1,
可 以 将 其 中 的 [0,1,1] 和 [1,−1] 都 替 换 成 上 述 对 应 的 {[0,1,b]|= k } 门 , 得 到 pl-Holant([0,1,b]|= k ) 的 实 例 G , 有
′

#(G ) = #(G) .
′

k k
图 4 一个实现 [0,1,b k−1 ] 函数的 {[0,1,b]|= k } 门, 黑色实心点表示二元函数 [0,1,b]

k k k k k k

图 5 一个 {[0,1,b]|= k } 门

[0, 1, 1] [0, 1, 1]

= k = k
[0, 1, 1] [0, 1, 1]
(a) 实现[0, 1] (b) 实现[0, 1] 2
⊗2
图 6 实现 [0,1] k ( 为奇数) 或 [0,1] ( k 为偶数) 的 {[0,1,b]|= k } 门

⊗2
若 k 为偶数, 利用两个 [0,1,1] 与一个 [0,1] ⊗2 相连可实现左侧函数 [1,1] ; 利用两个 [0,1,−1] 与一个 [0,1] ⊗2 相
⊗2 G #(G) 非 即 k 为偶数, 故
连可实现左侧函数 [1,−1] . 对于 pl-Holant({[0,1,1],[1,−1]}|= k ) 的任一实例 , 0 1, 由于
[1,−1] 在 G 中的出现次数必为偶数次, 通过调整, 在保持平面性的同时, 可以保持每个面内 [1,−1] 的个数是偶数.
利用实现 [1,−1] ⊗2 的 {[0,1,b]|= k } 门去替换同个面内相邻的成对 [1,−1]; 同时将其中的 [0,1,1] 也替换成对应的
′ ′
{[0,1,b]|= k } 门, 从而得到 pl-Holant([0,1,b]|= k ) 的实例 G , 有 #(G ) = #(G).
|V(G )| = O(|V(G)|), 且在多项式时
′
上述两种情况都是利用常数规模的 {[0,1,b]|= k } 门实现 [0,1,1] 和 [1,−1], 故
′
间内能构造出 G . 故定理得证.
λF 之间的替换, 但需要保证
在 mod p 环境下, 仍可以使用归一化操作, 将函数 F 替换为 λF, 来进行函数 F 和
λ mod p , 0.
引理 8. a, b 为两个有理数, 满足 (a,b) < {(1,−1),(−1,1)} 且 ab < {0,1}. 若 rETH 成立, 则存在 ε > 0, 对任意正整
√
数 k ⩾ 3 有 pl-Holant({[a,1,b],[0,1]}|= k ) 不能在 2 ε N 时间内计算, 其中 N 表示输入图的点数.
1 k −2
2
2
.
证明: 若 ab = −1, 即 [a,1,b] = [−1,b,b ], 有 b < {0,±1} k 为偶数时, 利用一个 (= k ) 与 个 [−1,b,b ] 相连,
b 2
形如图 6 中构件, 可得右侧二元函数 [±1,0,b k−2 ]; 进一步将该二元函数左右两端都与 [−1,b,b ] 相连, 则可以得到左
2
2
k
′
′ ′
.
′
′
′
侧二元函数 [b ±1,b k+1 ∓b,b k+2 ±b ], 归一化为 [a ,1,b ]. 容易验证, a b < {0,±1} 且 a , ±b k 为奇数时, 利用一个
k −1
k
2
k
2
(= k ) 与 个 [−1,b,b ] 相连, 得到右侧一元函数 [±1,b k−1 ]; 将其与 [−1,b,b ] 相连得到左侧 [b ±1,b(b ∓1)]; 再将
2
k −3
2 k k k k−2 (b ∓1)]. 进一步将该二元函数左右两端都
k
(= k ) 与 个 [−1,b,b ] 和一个 [b ±1,b(b ∓1)] 相连得到 [1±b ,0,b
2
2
k
2 k k k k+1 k k k+2 (b −1)+b (b +1)] 或
k
与 [−1,b,b ] 相连, 则可以得到左侧二元函数 [b (b −1)+(b +1),b (b −1)−b(b +1),b
k
k
k
k
2
k
k
k
[b (b +1)−(b −1),b k+1 (b +1)+b(b −1),b k+2 (b +1)−b (b −1)] , 记为 [α,β,γ] . 由于 b < {0,±1} 且 为有理数, 则
b