×

Which bases admit non-trivial shrinkage of formulae? (English) Zbl 0988.06009

Summary: We show that the shrinkage exponent, under random restrictions, of formulae over a finite complete basis \(B\) of Boolean functions, is strictly greater than 1 if and only if all the functions in \(B\) are unate, i.e., monotone increasing or decreasing in each of their variables. As a consequence, we get nonlinear lower bounds on the formula complexity of the parity function over any basis composed only of unate functions.

MSC:

06E30 Boolean functions
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
03D15 Complexity of computation (including implicit computational complexity)
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI