P集合 - mrsekut-p

P集合

定義 ref 『C言語による計算の理論』.icon p.156

$ \alphaは$ \{0,1\}^\astの部分集合とし、ある多項式時間チューリングマシン$ Mが存在する時、

任意の$ u\in\{0,1\}^\astに対して、以下が成り立つとき、$ \alphaをP集合、と言う

$ u\in\alphaならば、$ u\to^M 1

$ u\notin\alphaならば、$ u\to^M 0

例

$ \mathrm{equal}_{01}=\{u\in\{0,1\}^\ast|u内の0と1の出現回数が等しい\}　

これを計算するチューリングマシンの、計算ステップ数は入力の長さ$ nに対し、常に$ 2n^2+1以下になる