Lower bounds for computation with limited nondeterminism
Hartmut Klauck · 2002
We investigate the effect of limiting the number of available nondeterministic bits in different computational models. First we relate formula size to one-way communication complexity and derive lower bounds of /spl Omega/R(n/sup 2-/spl epsiv///log/sup 1-/spl epsiv//n) on the size of formulae with n/sup /spl epsiv///log/sup /spl epsiv//n, nondeterministic bits for 0