Here, Alice and Bob collectively constitute "Arthur", and the cost of an MAcc communication protocol is defined as the bit length of Merlin's message plus the communication cost of the ensuing randomized protocol between Alice and Bob. (Not charging for the length of Merlin's message would enable every function to be computed with constant cost in this model.)
Does not contain coNPcc (first shown by [Kla03]).
It is open to prove that there exists an explicit two-party function whose MAcc-type communication complexity is ω(n1/2).
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 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.
The corresponding model consists of randomized protocols such that yes-inputs are accepted with probability at least α and no-inputs are accepted with probability at most α/2 where α is to be thought of as a function of n. The cost of a protocol is defined to be its communication cost plus log(1/α).
Does not contain coNPcc [Raz92] [GW14].
Contains MAcc but does not equal it, since SBPcc is not closed under intersection [GLM+15].
Contained in AMcc and in PostBPPcc.
The complexity measure corresponding to SBPcc is equivalent to the "corruption bound" [GW14].
Similar to AMcc except that on each yes-input, the distribution of Merlin’s proof must leak no information about the input and moreover, this proof must be unique for each outcome of Arthur’s (i.e., Alice's and Bob's) randomness.
Unlike with other communication complexity classes, it is not known whether every function can be computed with O(n) communication in the ZAMcc model. In fact it is not even obvious that every function can be computed at all in this model, but this turns out to be the case; indeed, there is an O(2n) upper bound for every function [GPW16a].
Closely related to "private simultaneous messages" protocols in cryptography [AR16].