非決定性多項式時間

「Not-P」ではない！

「多項式時間で解けない問題のクラス」ではない

NP集合全体の集合

属するのは決定問題である

インフォーマルな定義

答えの証拠が与えられると、その証拠が本当に正しいかどうかを多項式時間で判定できる問題

この性質を多項式検証可能性という

定義 ref

非決定性チューリングマシンで多項式時間で解くことができる問題

NTIMEを使ったNPの定義 ref

\mathrm{NP}=\bigcup_{k\in\mathbb{N}}\mathrm{NTIME}(n^k)

クラスNPに属す問題の例

P. 有向グラフを見たときにハミルトン路があるかどうかの判定

NP. ハミルトン路を見た上で、ハミルトン路が存在することの判定

数独に例えると、数独の問題が与えられている状態で、

Pはその問題を解くこと

NPはこの問題がとききったものを見て、正しいかどうかを判定すること

ref p.321

参考

『計算理論の基礎 3』 p.315-

雑だが実際わかりやすかった