Non-deterministic communication complexity with few witnesses

Nondeterministic communication protocols in which no input has too many witnesses are studied. Two different lower bounds are presented for n_k(f), defined as the minimum complexity of a nondeterministic protocol for the function f in which each input has at most k witnesses. One result shows that n _k(f) is bounded below by Ω(√c( f)/k) where c(f) is the deterministic complexity. A second result bounds n_k( f) by log(rk(M_f))/k-1, where rk(M_f) is the rank of the representing matrix of f. It follows that the communication complexity analogue of the Turing-complexity class FewP is equal to the analogue of the class P