研究称构造无冒险布尔电路是 NP 难问题

工程师 Thomas Ahle 发推科普并展开线程介绍一项计算复杂性结论：构造无冒险（hazard-free）布尔电路是 NP 难问题。无冒险电路指当某个输入在 0/1 之间瞬变时输出保持稳定的电路。他用三值 Kleene 逻辑（位可取 0、1 或表示未知/不稳定的 u）来定义电路，并指出无冒险版本可能比普通电路指数级更昂贵。

2026-11-10 ~ 2026-11-10 · 2 条相关