Class Description

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

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

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.

More about...