P≠NP予想の主張の解説

P≠NP予想は計算量理論の話になります。

問題の集合（クラス）PとNPが等しくないという予想です。

• 「P」というのは，多項式時間で解ける問題のクラス，つまり「パソコンで解きやすい」問題です。
• 「NP」というのは，多項式時間で正解が本当に正しいか判定できる問題のクラスです。

もし，P=NPなら今まで解けなかったNPの問題が全て多項式時間で解けるようになってしまうので，そんな都合の良いことはないだろうという予想です。ちなみに，P=NPだと素因数分解の難しさを利用した現代の主要な暗号は破られてしまいます。

Pというのは，入力サイズに対して多項式時間で解ける問題のクラスです。

多項式時間かどうかというのは，四則演算や比較などのコンピュータ上での基本的な演算の回数で見積もります。

コンピュータを用いて指数時間かかってしまうような問題は現実的な時間で解くことができないのです。

例えば，$n^2$ 回計算が必要な問題は $n=10000$ くらいでも余裕で計算できますが，$2^n$ 回計算が必要な問題は $n=100$ でも到底計算できません。

NPというのは多項式時間で正解が本当に正しいか判定できる問題のクラスです。

答えを見つけるのは難しいかもしれないが，答えの正しさを証明するのなら簡単だ，という問題です。

オイラー閉路問題（例1）とハミルトン閉路問題（例2）は一見似ていますが，例1は簡単で例2は難しいというのは不思議ですね。

ちなみに，ハミルトン閉路問題は，有名な巡回セールスマン問題の特殊ケースとみなせます。

多項式時間で解けるなら，多項式時間で確認できるので，Pに属する問題はNPにも属します。つまりNPはPを含んでいます。

よって，P≠NP予想は，「NPに属するのにPに属さない問題(図の赤い部分)」があるのかどうかをめぐる問題ということになります。

そして，ハミルトン閉路問題など実際に図の赤い部分に属すると思われる問題が何千も見つかっています。しかし，それらがPに属さないことは証明されていません。