Class Description

PNPcc: Communication Complexity PNP

Not contained in PPcc [BVW07].

Does not contain BPPcc if partial functions are allowed [PPS14].

Contained in UPostBPPcc.

Linked From

BPPcc: Communication Complexity BPP

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

More about...


UPostBPPcc: Unrestricted Communication Analogue of PostBPP

Syntactically, this has the same relationship to PostBPPcc as UPPcc does to PPcc; i.e., we only allow private (no public) randomness, and do not charge for α in the cost of a protocol.

Contains PNPcc and hence does not equal PostBPPcc since it has been shown that PNPcc is not contained in PPcc much less in PostBPPcc [BVW07].

Contained in UPPcc.

More about...