# $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 < 1 ​ and ​ for all other inputs n,
g(n) = (log(n))1/(f(n)) < 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 < 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)$

• That's a very nice observation! Do you have any ideas on the other direction: is this class different from $NP^{cc}$? – ivmihajlin Feb 26 '17 at 0:01
• I just came up with and showed a result in the other direction, although it $\hspace{1.89 in}$ doesn't reach the class you're asking about. ​ ​ – user6973 Mar 1 '17 at 1:53