$NotTooManyP^{cc}$ class in communication complexity Class $P^{cc}$ is class of languages admitting deterministic communication protocol with polylog bits of communication.

Class $NP^{cc}$ is class of languages admitting nondeterministic communication protocol with polylog size witness.

Class  $FewP^{cc}$  is class of languages admitting nondeterministic communication protocol with polylog size witness, where each input has at most polylog correct witnesses.

It was proven that $FewP^{cc} = P^{cc}$ [1]. My question is about what happens if we allow not too many correct witnesses instead of few.

Let class $NotTooManyP^{cc}$ be class of languages admitting nondeterministic communication protocol with polylog size witness, where each input has at most polynomial correct witnesses. Is this class different from $P^{cc}$? If yes, how much weaker is this class then $NP^{cc}$?
When the inputs are the indicator functions, set non-disjointness is in NPcc with witnesses

from {0,1,2,3,...,n-2,n-1} $\big(\hspace{-0.04 in}$so in particular is in NotTooManyPcc$\hspace{-0.03 in}\big)$, ​ but by this paper,

the coUSBP (and thus also P) communication complexity of that problem is $\Theta$(n).

By padding, that means we leave coUSBPcc $\big(\hspace{-0.04 in}$and thus also Pcc$\hspace{-0.03 in}\big)$ ​ as soon

as the number of witnesses is no longer polylogarithmically-bounded.



Also, for all functions ​ f : {0,1,2,3,...} $\to$ (0,1] , ​ if the version with at most

nf(n) correct witnesses equals NPcc then f has a positive lower bound.

Proof:

Let f be any function from {0,1,2,3,...} to (0,1] such that the problem at

the start of this answer can be solved with at most nf(n) correct witnesses.

Let ​ g : {0,1,2,3,...} $\to$ {0,1,2,3,...} ​ be given by

g(0) = 0 = g(1) ​ and otherwise ​ g(n) = (log(n))1/(f(n)) ​ .

g(0) = 0 ​ and ​ g(1) = 0 &lt; 1 ​ and ​ for all other inputs n,

g(n) = (log(n))1/(f(n)) &lt; n1/(f(n)) ≤ n1/1 = n1 = n ​ .

Accordingly, consider the problem ​ ​ non-disjointness of subsets of ​ {0,1,2,3,...,(g(n))-2,(g(n))-1} ​ whose inputs are padded indicator functions.

By removing the padding, that problem can be solved with at most (g(n))f(n) correct witnesses.

For all integers n such that ​ 1 &lt; n , ​ (g(n))f(n) = $\big(\hspace{-0.05 in}$(log(n))1/(f(n))$\hspace{-0.03 in}\big)^{\hspace{.02 in}f\hspace{.02 in}(n)}$ = (log(n))(1/(f(n)))$\cdot$f(n) = (log(n))1 .

Thus the problem is in FewPcc, so by the result you mentioned, it's also in Pcc.

By the communication lower bound in this answer's starting sentence, that means g is

at most polylogarithmic, so 1/(f(n)) is bounded above, so f has a positive lower bound.



I'm not aware of any other results about limited-ambiguity versions of NPcc,

although with inputs as in the rest of this answer, (paddings of, if necessary) the problems

" ​ Does the intersection have at least _ elements? ​ "

seem like natural candidates for separating those classes.

$\big(\hspace{-0.04 in}$On the other hand, I wasn't even aware of ​ unambiguousPcc = Pcc ,

and still know neither a proof of that nor a reference for that.$\hspace{-0.03 in}\big)$