Ikenmeyer, Christian, Komarath, Balagopal, Lenzen, Christoph, Lysikov, Vladimir, Mokhov, Andrey and Sreenivasaiah, Karteek
(2019)
On the Complexity of Hazard-free Circuits.
JOURNAL OF THE ACM, 66 (4).
pp. 1-20.
Text
Ikenmeyer Komarath Lenzen Lysikov Mokhov Sreenivasaiah 2019 JACM On the complexity of Hazard-free Circuits.pdf - Published version Download (745kB) | Preview |
Abstract
The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows the existence of functions whose circuit complexity is polynomially bounded while every hazard-free implementation is provably of exponential size. Previous lower bounds on the hazard-free complexity were only valid for depth 2 circuits. The same proof method yields that every subcubic implementation of Boolean matrix multiplication must have hazards. These results follow from a crucial structural insight: Hazard-free complexity is a natural generalization of monotone complexity to all (not necessarily monotone) Boolean functions. Thus, we can apply known monotone complexity lower bounds to find lower bounds on the hazard-free complexity. We also lift these methods from the monotone setting to prove exponential hazard-free complexity lower bounds for non-monotone functions. As our main upper-bound result, we show how to efficiently convert a Boolean circuit into a bounded-bit hazard-free circuit with only a polynomially large blow-up in the number of gates. Previously, the best known method yielded exponentially large circuits in the worst case, so our algorithm gives an exponential improvement. As a side result, we establish the NP-completeness of several hazard detection problems.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Hazards, Boolean circuits, monotone circuits, computational complexity |
Depositing User: | Symplectic Admin |
Date Deposited: | 27 Nov 2019 10:56 |
Last Modified: | 19 Jan 2023 00:18 |
DOI: | 10.1145/3320123 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3063591 |