构造无冒险布尔电路是 NP-hard,无冒险版本可能指数级更贵

thomasahle · x · 2026-11-10

工程师 thomasahle 连续发帖科普布尔电路中的「冒险（hazard）」问题：用三值 Kleene 逻辑（位可取 0、1 或表示未知/不稳定的 u）定义电路，若电路对 bi=0 与 bi=1 输出同值，则 bi=u 时也应输出同值才算「无冒险」。

问题在于常见构造会产生冒险：例如 MUX(x,y,s)=(x&s)|(y&¬s) 在 MUX(1,1,u) 时输出 u 而非 1，「u」不再表现为「未知」。消除冒险需要额外门（如改为 (x&y)|((x&s)|(y&¬s))），而无冒险电路的代价可能呈指数级增长：附图定理表明，若判定 CLIQUE 的普通电路需要 n^Ω(jn) 规模，则存在一个多项式规模函数，其无 kn 位冒险的电路需要 2^Ω(kn) 个门；构造无冒险布尔电路本身是 NP-hard。