計算複雑性の話の中で、P、NP、NP完全、NP困難というキーワードが登場する。 それぞれの違いを、字面だけから判断するのは、少し無理そう。 それで、詳しい説明を Wikipedia に求めると・・・。 ・P(Wikipedai) ・NP(Wikipedai) ・NP完全(Wikipedai) ・NP困難(Wikipedai) 大学などで正確な定義を学習していない場合には、軽く絶望することになる。 そこで、厳密ではないことをあらかじめ断ったうえで、これらを簡単に説明してみる。 (証明されていないが、前提としてNP≠P とする。これが証明できたら100万ドルもらえる。) まず、それぞれの関係は下図のように表すことができる。 図では、上のものほど難しい問題で「P≦NP≦NP完全≦NP困難」と言うことができる。 さらに次のことが言える。 ・ P は現実的な時間で解を求めることができる問題。 ・ N