Class Description
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].
Linked From
BPP
cc: BPPcc in NOF model,
players
Has the same relation to BPPcc and BPP as P
cc does to Pcc and P.
NP
cc is not contained in BPP
cc for
players, for any constant
[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...