クラスNP
Non-deterministic Polynomial time
非決定性多項式時間
「Not-P」ではない！
「多項式時間で解けない問題のクラス」ではない
インフォーマルな定義
答えの証拠が与えられると、その証拠が本当に正しいかどうかを多項式時間で判定できる問題 $ \mathrm{NP}=\bigcup_{k\in\mathbb{N}}\mathrm{NTIME}(n^k)
クラスNPに属す問題の例
P. 有向グラフを見たときにハミルトン路があるかどうかの判定
NP. ハミルトン路を見た上で、ハミルトン路が存在することの判定
数独に例えると、数独の問題が与えられている状態で、
Pはその問題を解くこと
NPはこの問題がとききったものを見て、正しいかどうかを判定すること
ref 『計算理論の基礎 3』.icon p.321
参考
雑だが実際わかりやすかった