Premium
The effect of random restrictions on formula size
Author(s) -
Impagliazzo Russell,
Nisan Noam
Publication year - 1993
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240040202
Subject(s) - boolean function , upper and lower bounds , mathematics , function (biology) , combinatorics , parity (physics) , parity function , discrete mathematics , random variable , boolean expression , statistics , physics , quantum mechanics , mathematical analysis , evolutionary biology , biology
We consider the formula size complexity of boolean functions over the base consisting of ∧, ∨, and ¬ gates. In 1961 Subbotovskaya proved that, for any boolean function on n variables, setting all but a randomly chosen ϵ n variables to randomly chosen constants, reduces the expected complexity of the induced function by at least a factor. This fact was used by Subbotovskaya to derive a lower bound of Ω( n 1.5 ) for the formula size of the parity function, and more recently by Andreev who exhibited at lower bound of Ω C ( n 2.5 /log O (1) ( n )) for a function in P . We present the first improvement of Subbotovskaya's result, showing that the expected formual complexity of a function restricted as above is at most an O (ϵ γ ) franction of its original complexity, forThis allows us to give an improved lower bound of Ω( n 2.556… ) for Andreev's function. At the time of discovery, this was the best formula lower bound known for any function in NP. © 1993 John Wiley & Sons, Inc.