# Item

ITEM ACTIONSEXPORT

Released

Paper

#### On the Complexity of Hazard-free Circuits

##### Locator

There are no locators available

##### Fulltext (public)

arXiv:1711.01904.pdf

(Preprint), 310KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Ikenmeyer, C., Komarath, B., Lenzen, C., Lysikov, V., Mokhov, A., & Sreenivasaiah, K. (2017). On the Complexity of Hazard-free Circuits. Retrieved from http://arxiv.org/abs/1711.01904.

Cite as: http://hdl.handle.net/21.11116/0000-0000-3F22-4

##### 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.