Class Description

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.

Linked From

PNPcc: Communication Complexity PNP

Not contained in PPcc [BVW07].

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

Contained in UPostBPPcc.

More about...