多項式時間チューリングマシン
チューリングマシン
$ M
に対して、ある多項式
$ p
が存在して、任意の
$ u\in\{0,1\}^*
に対して以下が成り立つ時、
$ M
は多項式時間チューリングマシンであるという
$ M
を入力
$ u
で動作開始すると
$ p(|u|)
ステップ以内で停止する
補足
$ |u|
は、01の文字列
$ u
の長さ