Class Description

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.

Linked From

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

More about...


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


RPcc: Randomized Pcc

The class of functions which can be computed by players with access to shared random bits in the number-on-forehead (defined as in Pcc) model, subject to two constraints:

  1. The communication cost (the sum of the number of random bits used and bits written to the shared blackboard) is .
  2. If , then the players decide correctly with probably at least 2/3, whereas if , the players always decide correctly.

NPcc is not equal to RPcc for players, for any constant [DP08].

More about...