The analogue of Pcc for nondeterministic communication complexity. Both communication bits and nondeterministic guess bits count toward the complexity.
Does not equal Pcc or coNPcc because of the EQUALITY problem. Also, does not contain BPPcc because of that problem.
Is not contained in BPPcc (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 NPcc-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 NPcc is equivalent to the log of the number of rectangles needed to cover exactly the set of 1-entries of the communication matrix.
The analogue of Pcc for bounded-error probabilistic communication complexity.
Does not equal Pcc, and is not contained in NPcc, because of the EQUALITY problem.
If the classes are defined in terms of partial functions, then BPPcc
Has the same relation to NPcc and NP as Pcc does to Pcc and P.
NPcc is not contained in BPPcc for players, for any constant . As a result, NPcc is not equal to RPcc under the same conditions [DP08].
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. Pcc 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 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 NPcc and in BPPcc because of the EQUALITY problem.
If the classes are defined in terms of total functions, then Pcc = NPcc ∩ coNPcc = UPcc.
Defined in [BFS86].
The polynomial hierarchy for communication complexity, naturally built with NPcc and coNPcc forming the first level. Specifically, a cost-k protocol in the PHcc model corresponds to a constant-depth 2k-ary tree whose internal nodes are alternating layers of AND and OR gates, and whose leaves represent (the indicator functions of) either rectangles or complements of rectangles, as appropriate.
It is unknown whether Σ2cc equals Π2cc.
Defined in [BFS86], where it was also shown (among other things) that BPPcc is contained in Σ2cc ∩ Π2cc.
Similar to AMcc except that for each yes-input and each outcome of Arthur’s (i.e., Alice's and Bob's) randomness, there must be a unique proof Merlin can send that will be accepted.
Does not contain NPcc [GPW16a].
Is not contained in SBPcc [GPW16a], [GLM+15].
Is contained in PostBPPcc.
Similar to NPcc except that the protocol is restricted to have exactly one accepting computation on each yes-input.
The complexity measure corresponding to UPcc 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:
The quadratic overhead in simulating UPcc with Pcc, or equivalently the O(log2(n)) protocol for CISG, is known to be essentially optimal [GPW15].
