Title: Lower bounds for computation with limited nondeterminism
Abstract: 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</spl epsiv//spl les/1/2. Next we prove a rounds-communication hierarchy for communication complexity with limited nondeterminism solving an open problem. Given a bound s on the number of nondeterministic bits and a number k of rounds we construct a function which can be computed deterministically in k rounds with 0(sklogn) bits communication, but requires /spl Omega/(n/(s/sup 2/k/sup 2/logn)) in k-1 rounds though S nondeterministic bits are available. We apply this result to show a reversal hierarchy for 2-way automata with limited nondeterminism exhibiting exponential gaps. Furthermore we investigate the effect of limited nondeterminism on monotone circuit depth. All results presented in the paper have the common core that limited nondeterministic communication has high round dependence.
Publication Year: 2002
Publication Date: 2002-11-27
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 20
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot