Class Description

BPPcc: BPPcc in NOF model, players

Has the same relation to BPPcc and BPP as Pcc does to Pcc and P.

NPcc is not contained in BPPcc for players, for any constant [DP08].

Linked From

NPcc: NPcc in NOF model, players

Has the same relation to NPcc and NP as Pcc does to Pcc and P.

NPcc is not contained in BPPcc for players, for any constant . As a result, NPcc is not equal to RPcc under the same conditions [DP08].

More about...


Pcc: Pcc in NOF model, players

Like Pcc, but with players, where each player can see all of the other player's bits, but not their own. Intuitively, each player has their bits written on their forehead.

More formally, Pcc is the class of functions where for all , , such that is solvable in a deterministic sense by players, each of which is aware of all inputs other than his own, and such that bits of communication are used.

Pcc is trivially contained in BPPcc, RPcc and NPcc.

More about...