Class Description

P^cc: Communication Complexity P

In a two-party communication complexity problem, Alice and Bob have n-bit strings x and y respectively, and they wish to evaluate some Boolean function f(x,y) using as few bits of communication as possible. P^cc is the class of (infinite families of) f's, such that the amount of communication needed is only O(polylog(n)), even if Alice and Bob are restricted to a deterministic protocol.

Note that all functions of the form above are solvable given ${\displaystyle O(n)}$ bits of communication, since no bounds are placed on the computational abilities of Alice and Bob. Thus, when discussing this class, "polynomially" is sometimes used in place of "polylogarithmically."

Is strictly contained in NP^cc and in BPP^cc because of the EQUALITY problem.

If the classes are defined in terms of total functions, then P^cc = NP^cc ∩ coNP^cc = UP^cc.

Defined in [BFS86].

Linked From

BPP^cc: Communication Complexity BPP

The analogue of P^cc for bounded-error probabilistic communication complexity.

Does not equal P^cc, and is not contained in NP^cc, because of the EQUALITY problem.

If the classes are defined in terms of partial functions, then BPP^cc

• is not contained in P^NPcc [PPS14];
• does not contain NP^cc ∩ coNP^cc [Kla03].

More about...

BPP_{${\displaystyle k}$}^cc: BPP^cc in NOF model, ${\displaystyle k}$ players

Has the same relation to BPP^cc and BPP as P_{${\displaystyle k}$}^cc does to P^cc and P.

NP_{${\displaystyle k}$}^cc is not contained in BPP_{${\displaystyle k}$}^cc for ${\displaystyle k\leq (1-\delta )\cdot \log n}$ players, for any constant ${\displaystyle \delta >0}$ [DP08].

More about...

NP^cc: Communication Complexity NP

The analogue of P^cc for nondeterministic communication complexity. Both communication bits and nondeterministic guess bits count toward the complexity.

Does not equal P^cc or coNP^cc because of the EQUALITY problem. Also, does not contain BPP^cc because of that problem.

Is not contained in BPP^cc (first shown by [BFS86]).

SET-INTERSECTION, in which Alice's and Bob's strings are identified with characteristic vectors of sets and yes-inputs are intersecting while no-inputs are disjoint, is the canonical NP^cc-complete problem. Sometimes SET-DISJOINTNESS also refers to this problem, but sometimes it refers to the complement of this problem.

The complexity measure corresponding to NP^cc is equivalent to the log of the number of rectangles needed to cover exactly the set of 1-entries of the communication matrix.

More about...

NP_{${\displaystyle k}$}^cc: NP^cc in NOF model, ${\displaystyle k}$ players

Has the same relation to NP^cc and NP as P_{${\displaystyle k}$}^cc does to P^cc and P.

NP_{${\displaystyle k}$}^cc is not contained in BPP_{${\displaystyle k}$}^cc for ${\displaystyle k\leq (1-\delta )\cdot \log n}$ players, for any constant ${\displaystyle \delta >0}$. As a result, NP_{${\displaystyle k}$}^cc is not equal to RP_{${\displaystyle k}$}^cc under the same conditions [DP08].

More about...

P_{${\displaystyle k}$}^cc: P^cc in NOF model, ${\displaystyle k}$ players

Like P^cc, but with ${\displaystyle k}$ players, where each player can see all of the other player's bits, but not their own. Intuitively, each player has their bits written on their forehead.

More formally, P_{${\displaystyle k}$}^cc is the class of functions ${\displaystyle F:X_{1}\times X_{2}\times \cdots \times X_{k}\to \{0,1\}}$ where for all ${\displaystyle i\in [1..k]}$, ${\displaystyle X_{k}\in \{0,1\}^{n}}$, such that ${\displaystyle F}$ is solvable in a deterministic sense by ${\displaystyle k}$ players, each of which is aware of all inputs ${\displaystyle X_{i}}$ other than his own, and such that ${\displaystyle O\left(\mathrm {poly} (\log n)\right)}$ bits of communication are used.

P_{${\displaystyle k}$}^cc is trivially contained in BPP_{${\displaystyle k}$}^cc, RP_{${\displaystyle k}$}^cc and NP_{${\displaystyle k}$}^cc.

More about...

RP^cc: Communication Complexity RP

The analogue of P^cc for bounded one-sided error probabilistic communication complexity.

Contains the complement of the EQUALITY problem.

More about...

UP^cc: Communication Complexity UP

Similar to NP^cc except that the protocol is restricted to have exactly one accepting computation on each yes-input.

The complexity measure corresponding to UP^cc is equivalent to the log of the number of rectangles needed to partition the set of 1-entries of the communication matrix.

Introduced in [Yan91], where it was shown that for total functions:

• P^cc=UP^cc.
• The "Clique vs. Independent Set problem" CIS_G on a graph G (Alice gets a clique, Bob gets an independent set: do they intersect?) is "complete" for UP^cc in the sense that every f, say with UP^cc(f)=c, reduces to CIS_G for some G on 2^c many nodes.

The quadratic overhead in simulating UP^cc with P^cc, or equivalently the O(log²(n)) protocol for CIS_G, is known to be essentially optimal [GPW15].

More about...

ZPP^cc: Communication Complexity ZPP

Equals P^cc if defined in terms of total functions; is not contained in ⊕P^cc if defined in terms of partial functions [GPW16b].

More about...