NP集合
定義 ref 『C言語による計算の理論』.icon p.159
$ \alphaは$ \{0,1\}^\astの部分集合とする
$ u\in\alphaならば、$ Mを入力$ uで動作開始すると、
可能な実行過程の内少なくとも1つでは1を出力して停止する
$ u\notin\alphaならば、$ Mを入力$ uで動作開始すると
どんな実行過程を経ても0を出力して停止する
例
$ \mathrm{hamilton}=\{u\in\{0,1\}^\ast|uはハミルトン閉路を持つグラフを表す\}
こんな$ Mを用意する
①拡張点をちょうど1個ずつ含む頂点列を一つだけ非決定的に生成して、テープに書き込み、
②その列を辿った後に出発点に戻る経路が、入力されたグラフの上でハミルトン閉路になっていれば1を、なっていなければ0を返す
集合内の条件より、$ uは、ハミルトン閉路を必ず持つが
$ Mが、その経路を一発で出してくれるとは限らない
①で生成したものは一つの頂点列なので、$ Mの1回の実行自体は多項式時間で停止する
ある$ u'を持ってきて、これが「$ \mathrm{hamilton}に含まれているかどうか」を確認するためにはものすごい時間がかかる