チューリングマシンMに対して、ある多項式pが存在して、任意のu\in\{0,1\}^*に対して以下が成り立つ時、Mは多項式時間チューリングマシンであるという

Mを入力uで動作開始するとp(|u|)ステップ以内で停止する

補足

|u|は、01の文字列uの長さ