4
$\begingroup$

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}$?

$\endgroup$
1
$\begingroup$

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)$

$\endgroup$
  • $\begingroup$ That's a very nice observation! Do you have any ideas on the other direction: is this class different from $NP^{cc}$? $\endgroup$ – ivmihajlin Feb 26 '17 at 0:01
  • $\begingroup$ 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. ​ ​ $\endgroup$ – user6973 Mar 1 '17 at 1:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.