Class Description

P_{${\displaystyle k}$}^cc: P^cc in NOF model, ${\displaystyle k}$ players

Like P^cc, but with ${\displaystyle k}$ 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_{${\displaystyle k}$}^cc is the class of functions ${\displaystyle F:X_{1}\times X_{2}\times \cdots \times X_{k}\to \{0,1\}}$ where for all ${\displaystyle i\in [1..k]}$, ${\displaystyle X_{k}\in \{0,1\}^{n}}$, such that ${\displaystyle F}$ is solvable in a deterministic sense by ${\displaystyle k}$ players, each of which is aware of all inputs ${\displaystyle X_{i}}$ other than his own, and such that ${\displaystyle O\left(\mathrm {poly} (\log n)\right)}$ bits of communication are used.

P_{${\displaystyle k}$}^cc is trivially contained in BPP_{${\displaystyle k}$}^cc, RP_{${\displaystyle k}$}^cc and NP_{${\displaystyle k}$}^cc.

Linked From

BPP_{${\displaystyle k}$}^cc: BPP^cc in NOF model, ${\displaystyle k}$ players

Has the same relation to BPP^cc and BPP as P_{${\displaystyle k}$}^cc does to P^cc and P.

NP_{${\displaystyle k}$}^cc is not contained in BPP_{${\displaystyle k}$}^cc for ${\displaystyle k\leq (1-\delta )\cdot \log n}$ players, for any constant ${\displaystyle \delta >0}$ [DP08].

More about...

NP_{${\displaystyle k}$}^cc: NP^cc in NOF model, ${\displaystyle k}$ players

Has the same relation to NP^cc and NP as P_{${\displaystyle k}$}^cc does to P^cc and P.

NP_{${\displaystyle k}$}^cc is not contained in BPP_{${\displaystyle k}$}^cc for ${\displaystyle k\leq (1-\delta )\cdot \log n}$ players, for any constant ${\displaystyle \delta >0}$. As a result, NP_{${\displaystyle k}$}^cc is not equal to RP_{${\displaystyle k}$}^cc under the same conditions [DP08].

More about...

RP_{${\displaystyle k}$}^cc: Randomized P_{${\displaystyle k}$}^cc

The class of functions ${\displaystyle F}$ which can be computed by ${\displaystyle k}$ players with access to shared random bits in the number-on-forehead (defined as in P_{${\displaystyle k}$}^cc) 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 ${\displaystyle O({\textrm {polylog}}(n))}$.
2. If ${\displaystyle F(X_{1},\dots ,X_{k})=1}$, then the players decide correctly with probably at least 2/3, whereas if ${\displaystyle F(X_{1},\dots ,X_{k})=0}$, the players always decide correctly.

NP_{${\displaystyle k}$}^cc is not equal to RP_{${\displaystyle k}$}^cc for ${\displaystyle k\leq (1-\delta )\cdot \log n}$ players, for any constant ${\displaystyle \delta >0}$ [DP08].

More about...