论文标题
关于无危险电路的注释
Notes on Hazard-Free Circuits
论文作者
论文摘要
构建无风险的布尔电路（避免电子故障的电路）的问题可以追溯到1940年代，并且是电路设计甚至网络安全方面的重要问题。我们表明，当电路（纯粹是语法上）所有素数以及它计算的布尔函数的所有主要含义时，Demorgan电路是无危险的。这扩展到任意Demorgan电路，这是Eichelberger的经典结果[IBM J. Res。开发。，9（1965）]显示了特殊深度两回电的属性。通过一个非常简单的证据，我们还加强了Ikenmeyer等人最近的结果。 [J。 ACM，66：4（2019）]：单调布尔函数的无危险和单调电路的复杂性确实是一致的，而且每个单调布尔函数的每个最佳无风险电路都必须是单调的。然后，我们表明，非常简单（非单调）布尔函数的无危险电路复杂性在超级多个函数上大于其无限制的电路复杂性。此函数接受布尔值n x n矩阵IFF每行，每一列都有一个1输入。最后，我们表明，N变量的每个布尔函数都可以通过大小O（2^n/n）的无危险电路来计算。
The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s and is an important problem in circuit design and even in cybersecurity. We show that a DeMorgan circuit is hazard-free if and only if the circuit produces (purely syntactically) all prime implicants as well as all prime implicates of the Boolean function it computes. This extends to arbitrary DeMorgan circuits a classical result of Eichelberger [IBM J. Res. Develop., 9 (1965)] showing this property for special depth-two circuits. Via an amazingly simple proof, we also strengthen a recent result Ikenmeyer et al. [J. ACM, 66:4 (2019)]: not only the complexities of hazard-free and monotone circuits for monotone Boolean functions do coincide, but every optimal hazard-free circuit for a monotone Boolean function must be monotone. Then we show that hazard-free circuit complexity of a very simple (non-monotone) Boolean function is super-polynomially larger than its unrestricted circuit complexity. This function accepts a Boolean n x n matrix iff every row and every column has exactly one 1-entry. Finally, we show that every Boolean function of n variables can be computed by a hazard-free circuit of size O(2^n/n).
