はじめに
今回はP，NP，NP完全，NP困難について書いていきたいと思います。
私自身習いたてなので、本当に備忘録というかメモ程度なのであしからず。
前置き
問題はそれぞれ異なる難しさを持っています。これらを比較は帰着によってする必要があります。
問題を難しさの度合いによってクラス分けしたものがP，NP等になります。
多くの科学者はだと予想しているので、左のような関係にあると言われています。
P
まずP，NPは判定問題について扱います。
判定問題というのは「Yes か No かを判定する問題」のことですね。
これを前提に、Pは多項式時間で解ける問題の集合です。
NP
NPは”証拠”が与えられた時、その証拠が本当かどうかを多項式時間で検証できる問題の集合です。
つまり少なくとも答え合わせなら多項式時間で分かるという認識で良さそうです。
NP困難
NP困難はNPに含まれる全てのの問題から多項式時間帰着できる問題の集合です。
多項式時間帰着について最後に付録として書きますが、多項式時間帰着ができればNPのどの問題よりも同等かそれ以上に難しいことが示されます。
またPやNPは判定問題を対象としていますが、判定問題でない問題はNP困難として扱うみたいです。
NP完全
NP完全はNPであり、かつNP困難である問題の集合です。
NP に属する問題の中で最も難しい問題という認識で良いみたい。
という前提が成り立つなら、NP完全，NP困難は多項式時間では解けないです。
またNP完全であることの証明をしたい場合は「クラスNPに属す かつ 既にNP完全性が知られている問題から多項式時間帰着する」ことができればOKになります。
多項式時間帰着
付録として多項式時間帰着について説明を書いておきます。
まず前提として以下がなりたつことを帰着といいます。
AのYESのインスタンスはBのYESのインスタンスに
AのNOのインスタンスはBのNOのインスタンスに
この前提を念頭におきながら、多項式時間帰着とは多項式時間で実行できる帰着のことです。
これは成り立つ時BはAと同等かそれ以上に難しいということが分かります。
例えば問題Bが多項式時間で解けるなら「BはAと同等かそれ以上に難しい」ので、Aも多項式時間で解けるということになります。
