Class Description
The class of functions
which can be computed by
players with access to shared random bits in the number-on-forehead (defined as in P
cc) model, subject to two constraints:
- The communication cost (the sum of the number of random bits used and bits written to the shared blackboard) is
. - If
, then the players decide correctly with probably at least 2/3, whereas if
, the players always decide correctly.
NP
cc is not equal to RP
cc for
players, for any constant
[DP08].
Linked From
NP
cc: NPcc in NOF model,
players
Has the same relation to NPcc and NP as P
cc does to Pcc and P.
NP
cc is not contained in BPP
cc for
players, for any constant
. As a result, NP
cc is not equal to RP
cc under the same conditions [DP08].
More about...
P
cc: 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, P
cc 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.
P
cc is trivially contained in BPP
cc, RP
cc and NP
cc.
More about...