Class Description

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].

Linked From

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].

More about...