Class Description

P^NPcc: Communication Complexity P^NP

Not contained in PP^cc [BVW07].

Does not contain BPP^cc if partial functions are allowed [PPS14].

Contained in UPostBPP^cc.

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

UPostBPP^cc: Unrestricted Communication Analogue of PostBPP

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

Contains P^NPcc and hence does not equal PostBPP^cc since it has been shown that P^NPcc is not contained in PP^cc much less in PostBPP^cc [BVW07].

Contained in UPP^cc.

More about...