PとNPとNP完全とNP困難 - 大人になってからの再学習

計算複雑性の話の中で、P、NP、NP完全、NP困難というキーワードが登場する。
それぞれの違いを、字面だけから判断するのは、少し無理そう。
それで、詳しい説明を Wikipedia に求めると・・・。

・P（Wikipedai）
・NP（Wikipedai）
・NP完全（Wikipedai）
・NP困難（Wikipedai）

大学などで正確な定義を学習していない場合には、軽く絶望することになる。

そこで、厳密ではないことをあらかじめ断ったうえで、これらを簡単に説明してみる。
（証明されていないが、前提としてNP≠P とする。これが証明できたら100万ドルもらえる。）

まず、それぞれの関係は下図のように表すことができる。

図では、上のものほど難しい問題で「P≦NP≦NP完全≦NP困難」と言うことができる。

さらに次のことが言える。
・ P は現実的な時間で解を求めることができる問題。
・ NP, NP完全, NP困難は、現実的な時間で解を求めることができない（ある程度の諦めと妥協が必要な問題）。
・ NP完全は、NPの中で最も難しい問題。
・ NP困難は、NPである場合も、NPでない場合もあり、NP完全と同等かそれ以上に難しい問題。（NPではない場合があることに注意）

まずは最低限、これだけでも知った上で学習を進めるといい。

ちなみに、ある問題AがNP完全であることは、一般に次のようにして証明される。
(1) 問題AがNPに属することを示す。
(2) NP完全であることが既知の問題aを、多項式時間で問題Aに変換可能であることを示す。
(3) 以上より、 A は a と同等かそれより難しい。しかし、NP完全問題は NPの中で一番難しい問題なので、Aはaと同じくNP完全問題である。
このような証明では、既知のNP完全問題 a として「3-SAT問題」が使用されることが多い。