Multilevel [Boolean] formulas

DNF formulas always have depth 2. By allowing larger depths one can potentially find smaller formulas for functions. A major result from the 1980s is that it requires a formula with depth at least Log[n]/(c + Log[Log[n]]) to make it possible to represent an Xor of n variables using a polynomial number of And, Or and Not operations. If one chooses an n-variable Boolean function at random out of the 2^^{2}^^{n} possibilities, it is typical that regardless of depth a formula involving at least 2^^{n}/n operations will be needed to represent it. A formula of polynomial size and logarithmic depth exists only when a function is the computational complexity class NC discussed on page 1149.

Little is known about systematic minimization of Boolean formulas with depths above 2. Nevertheless, some programs for circuit design such as SIS do include a few heuristics. And this for example allows SIS to generate higher depth formulas somewhat smaller than the minimal DNF for the first three steps of rule 30 evolution.