2014/06/22

P≠NP予想の主張の解説

分野: その他

ミレニアム問題とは,解決したら100万ドルもらえる重大な7つの問題です。7つのうちポアンカレ予想だけは既に解かれています。
残り6つのうち,主張が比較的理解しやすいのはP≠NP予想とリーマン予想です。そこでこのページではP≠NP予想の主張について解説します。

大雑把な解説

P≠NP予想は計算量理論の話になります。
問題の集合(クラス)PとNPが等しくないという予想です。

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

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

クラスPとは

Pというのは入力サイズに対して多項式時間で解ける問題のクラスです。
多項式時間かどうかというのは,四則演算や比較などのコンピュータ上での基本的な演算の回数で見積もります。

コンピュータを用いて指数時間かかってしまうような問題は現実的な時間で解くことができないのです。
($n^2$ 回計算が必要な問題は $n=10000$ くらいでも余裕で計算できるが,$2^n$ 回計算が必要な問題は $n=100$ でも到底計算できない)

例1

与えられたグラフが一筆書きできるか判定する問題はPである。なぜなら,各頂点の次数が偶数かどうかを調べればよいので,高々「頂点の数×辺の数」くらいの演算をすればよい。→オイラーグラフの定理とその証明

クラスNPとは

NPというのは多項式時間で正解が本当に正しいか判定できる問題のクラスです。
答えを見つけるのは難しいかもしれないが,答えの正しさを証明するのなら簡単だ,という問題です。

例2

ハミルトン閉路問題(頂点を1回ずつ通って元に戻ってくる道があるのか判定する問題)はNPである。実際にそのような道を探すのは難しい(多項式時間で解く方法は発見されていない)が,答えが与えられたらそれが確かに正しいということは簡単に確認できる。

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

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

PとNPの包含関係

P≠NP予想

多項式時間で解けるなら,多項式時間で確認できるので,Pに属する問題はNPにも属します。つまりNPはPを含んでいます。
よって,P≠NP予想は,「NPに属するのにPに属さない問題(図の赤い部分)」があるのかどうかをめぐる問題ということになります。
そして,ハミルトン閉路問題など実際に図の赤い部分に属すると思われる問題が何千も見つかっているのです。しかし,それらがPに属さないことは証明されていません。

P≠NP予想が解けたら約一億円もらえるのでみなさん挑戦してみてください
分野: その他