非決定性有限オートマトンっぽく動くチューリングマシン

状態とヘッドに対して、次の動作の候補が複数ある

非決定性TM Mに対して、ある多項式pが存在して、任意のu\in\{0,1\}^\astに対して、次が成り立つ時、Mは非決定性多項式時間チューリングマシン

Mを入力uで動作開始すると、どんな動作過程を経てもp(|u|)ステップ以内で停止する