NPに対する理解

間違っていると思うけど、整理のためにとりあえずまとめる。

追記
クラスNPの定義は
非決定性チューリングマシンで多項式時間で解けること
非決定性チューリングマシンとは、いろいろな分岐をすべて同時並行的に調べ尽くしてしまうようなもの（まだ存在しない）
【計算量理論の初歩】量子コンピュータの優位性はいかに！？ - HELLO CYBERNETICS

追記終わり

問題は以下の2つに分けられる
・時間をかければ解ける問題：クラスNP
・時間をかけても解けない問題：クラスNPに属していない

クラスPについて
時間をかければ解ける問題(クラスNP)の中でも、簡単なものをクラスPと呼ぶ

NP困難について
以下の2つを満たすとNP困難と呼ぶ
・NP以上に複雑な問題
（クラスNPに属するNP困難とクラスNPに属さないNP困難がある）
・すべてのNP問題が帰着できる問題
（NP問題をわざわざより複雑な問題(NP困難)へと変形できる）

NP完全について
・NP困難の中でも、クラスNPに属する問題をNP完全と呼ぶ
・NP完全が効率よく解ければクラスNPの問題全ても効率よく解ける
（クラスNPの複雑さ ＝ NP完全の複雑さ ＋ 多項式時間）