论文标题
关于检测危险的复杂性
On the complexity of detecting hazards
论文作者
论文摘要
在布尔电路中检测和消除逻辑危害是逻辑电路设计中的一个基本问题。我们表明，没有任何$ o（3^{（1-ε）n} \ text {poly}（s））$ time算法，对于任何$ε> 0 $，它检测到$ n $变量的布尔电路中的逻辑危害，在$ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $。即使输入电路被限制为深度四的公式，该下限也保持。我们还提出了一种多项式时间算法，用于检测DNF中的$ 1 $ -HAZARDS（OR，CNF中的$ 0 $ -HAZARDS）公式。由于DNF中的$ 0 $ - 税收（或CNF中的$ 1 $ - 删除）公式很容易消除，因此该算法可用于检测给定的DNF或CNF公式在实践中是否具有危险。
Detecting and eliminating logic hazards in Boolean circuits is a fundamental problem in logic circuit design. We show that there is no $O(3^{(1-ε)n} \text{poly}(s))$ time algorithm, for any $ε> 0$, that detects logic hazards in Boolean circuits of size $s$ on $n$ variables under the assumption that the strong exponential time hypothesis is true. This lower bound holds even when the input circuits are restricted to be formulas of depth four. We also present a polynomial time algorithm for detecting $1$-hazards in DNF (or, $0$-hazards in CNF) formulas. Since $0$-hazards in DNF (or, $1$-hazards in CNF) formulas are easy to eliminate, this algorithm can be used to detect whether a given DNF or CNF formula has a hazard in practice.
