クラス P

言語 $L \subseteq \Sigma^{*}$ が $\mathrm{P}$ に属するとは、決定性チューリング機械 $M$ と多項式 $p$ が存在して、次の 2 条件がともに成り立つことをいいます。

1. すべての入力 $x \in \Sigma^{*}$ に対し、$M$ は高々 $p(|x|)$ ステップで停止する。
2. すべての $x \in \Sigma^{*}$ に対し、$M$ が $x$ を受理することと $x \in L$ であることが同値である。

このような $L$ の全体を $\mathrm{P}$ と書きます。