Shrinkage of de Morgan formulae under restriction
Michael Stewart Paterson, Uri Zwick · Random Structures and Algorithms · 1993
Abstract It is shown that a random restriction leaving only a fraction ϵ of the input variables unassigned reduces the expected de Morgan formula size of the induced function by a factor ofO(E(5−√2)/2) =O(ϵ1.63). (A de Morgan, or unate, formula is a formula over the basis {∧, ∨, ¬}.) This improves a long‐standing result ofO(ϵ1.5) by Subbotovskaya and a recent improvement toO(ϵ(21−√73)/8) =O(ϵ1.55) by Nisan and Impagliazzo. The New exponent yields an increased lower bound ofn(7−√3)/2−o(1)= Ω(n2.63) for the de Morgan formula size of a function in P defined by Andreev. This is the largest formula size lower bound known, even for functions in NP. © 1993 John Wiley & Sons, Inc.