Class Description

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.

Linked From

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.

More about...