非決定性チューリングマシン
nondeterministic Turing Machine
非決定性有限オートマトン
っぽく動く
チューリングマシン
状態とヘッドに対して、次の動作の候補が複数ある
非決定性多項式時間チューリングマシン
非決定性TM
$ M
に対して、ある多項式
$ p
が存在して、任意の
$ u\in\{0,1\}^\ast
に対して、次が成り立つ時、
$ M
は非決定性多項式時間チューリングマシン
$ M
を入力
$ u
で動作開始すると、どんな動作過程を経ても
$ p(|u|)
ステップ以内で停止する
https://ja.wikipedia.org/wiki/非決定性チューリングマシン