On the Complexity of Hazard-Free Formulas

This article studies the hazard-free formula complexity of Boolean functions. Hazard-free formulas are De Morgan formulas that may take input variables with an unknown value, but produce a Boolean output whenever it can be determined by the known bits. Our first result concerns the hazard-derivative approach of Ikenmeyer et al. (J. ACM, 2019) for proving lower bounds in the hazard-free model. We show that this approach yields optimal bounds only for unate functions, i.e., the monotone formula complexity of a hazard-derivative equals the hazard-free formula complexity of the function itself. Our second result proves that the hazard-free formula complexity of a uniformly random Boolean function is at most \(2^{(1+o(1))n}\) . Previously, no better upper bound than \(O(3^n)\) was known. Notably, unlike in the general Boolean case, where the typical formula complexity is derived from that of the multiplexer function with n -bit selector, the hazard-free formula complexity of a random function is smaller than the optimal hazard-free formula for the multiplexer by an exponential factor in n . We provide two proofs of this fact. The first is direct, bounding the number of prime implicants of a random Boolean function and constructing a DNF of the claimed size. The second introduces a new and independently interesting result: a weak converse to the hazard-derivative lower bound method, which gives an upper bound on the hazard-free complexity of a function in terms of the monotone complexity of a subset of its hazard-derivatives. Additionally, we explore the hazard-free formula complexity of block composition and obtain a hazard-free analogue of the result of Karchmer, Raz, and Wigderson (Computational Complexity, 1995) in the monotone setting. Our result implies a stronger lower bound on the hazard-free formula depth of the block composition of the set covering function with the multiplexer function than the bound obtained via the hazard-derivative method.