Class Description

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

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