NONDETERMINISTIC COMMUNICATION COMPLEXITY WITH FEW WITNESSES

We study non-deterministic communication protocols in which no input h as too many witnesses. Define n(k)(f) to be the minimum complexity of a non-deterministic protocol for the function f in which each input ha s at most k witnesses. We present two different lower bounds for n(k)( f). Our first results shows that n(k)(f) is bounded below by OMEGA(squ are-root c(f)/k), where c(f) is the deterministic complexity. Our seco nd results bounds n(k)(f) by log(rk(M(f)))/k - 1, where rk(M(f)) is th e rank of the representing matrix of f. As a consequence, it follows t hat the communication complexity analogue of the Turning-complexity cl ass FewP is equal to the analogue of the class P. (C) 1994 Academic Pr ess, Inc.