<p>Class $P^{cc}$ is class of languages admitting deterministic communication protocol with <strong><em>polylog</em></strong> bits of communication.</p>

<p>Class $NP^{cc}$ is class of languages admitting nondeterministic communication protocol with <strong><em>polylog</em></strong> size witness.</p>

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

<p>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.</p>

<p>Let class $NotTooManyP^{cc}$ be class of languages admitting nondeterministic communication protocol with <strong><em>polylog</em></strong> size witness, where each input has at most <strong><em>polynomial</em></strong> correct witnesses. Is this class different from $P^{cc}$? If yes, how much weaker is this class then $NP^{cc}$?</p>

<complexity-classes><communication-complexity><nondeterminism>
$NotTooManyP^{cc}$ class in communication complexity
ivmihajlin
# $NotTooManyP^{cc}$ class in communication complexity

(Asked by: username_0 on 2017-02-25)

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

**Tags:** complexity-classes, communication-complexity, nondeterminism

---

## 0 answers

