数学の未解決問題の1つP対NP問題。
1億円の懸賞金がかけられた、ミレニアム問題の1つでもあります。
この問題の内容と解き方についてわかりやすく解説します。
- 数学の未解決問題が好き
- P対NP問題をわかりやすく解説してほしい
- 一攫千金を狙っている
P対NP問題とは？
P対NP問題は数学の未解決問題であり、1億円の懸賞金がかけられたミレニアム問題の1つでもあります。
P対NP問題は
- P=NPなのか？
- P≠NPなのか？
を問われているため、まずは「P問題」と「NP問題」が何かを理解する必要があります。
NP問題とは？
NP問題とは、多項式時間以内で解くことができる問題のことです。
簡単に表現すると「しらみつぶしに調べればいつか解ける問題」となります。
具体的には以下の問題がNP問題になります。
巡回セールスマン問題
セールスマンがいくつかの家を1度ずつ訪問して戻ってくるとき、移動時間が最短になる経路を求める問題です。
訪問先の数を\(n\)としたとき、選択肢の総数は\(\displaystyle \frac{n!}{2n}\)通りになります。
訪問先が28件あったとすると
ナップサック問題
ナップサックにいくつかの品物を詰め込むとき、総金額を最大にするパターンを求める問題です。
出展：wikipedia
品物には金額とサイズが与えられていて、ナップサックの容量以上に品物を詰め込むことはできません。
ぷよぷよの連鎖問題
実はパズルゲームのぷよぷよにもNP問題が存在しています。
「与えられたぷよで\(n\)連鎖以上可能か？」
この問題はしらみつぶしに調べないと答えを求めることができません。
P問題とは？
P問題とは、多項式時間以内で解くことができるアルゴリズムが存在する問題のことです。
簡単に表現すると「NP問題のようだが、簡単に解くコツがある問題」となります。
具体的には以下の問題がP問題になります。
ケーニヒスベルクの問題(一筆書き問題)
出展：wikipedia
1735年に天才数学者オイラーが証明した問題です。
どんな図形でも一筆書きできるかを簡単に判断することができます。
実は一筆書き問題を簡単に解くコツが存在します。なんとこのコツを知っていれば、その図形が一筆書きが可能か判断でき、スタートとゴールの点もどこかわかってしまうのです。この記事では「一筆書き問題を簡単に解くコツ」から「コツが発見さ[…]
素数判定問題
ある数\(n\)が素数かどうか？を確認するためには、\(n\)未満の素数全てで割り切れないことを確認する必要がありました。
しかし2002年にAKS素数判定法が発見されました。
AKS素数判定法を使えば、\(n\)が素数かどうかを判定することができます。
判定対象の数を\(n\)とする。
- \(n=a^b\)であれば\(n\)は素数ではない。(\(a,b\)は自然数、\(b>1\))
- \(o_r(n)>\log^2n\)となるような最小の数\(r\)を求める。
\(o_r(n)\)は\(n^e\equiv1(\mod r )\)を満たす\(e\)を指す。 - \(a≤r\)となる\(a\)のいずれかが\(1＜(a,n)<n\)を満たす場合、\(n\)は素数ではない。
(\(a,n\))は\(a\)と\(n\)の最大公約数である。 - \(n≤r\)ならば\(n\)は素数である。
- \(1≤a≤[\sqrt{φ(r)} \log{n}]\)の範囲\(a\)に対して\((X＋a)^n≢X^n＋a(\mod X^r-1,n )\)ならば\(n\)は素数ではない。
- \(n\)は素数。
P対NP問題の解き方
P対NP問題は
- P=NPなのか？
- P≠NPなのか？
を問われている問題です。
つまり
- 全てのNP問題には簡単に解くコツがあるのか？
- 簡単に解くコツがなく、しらみつぶしに調べるしかない問題が存在するのか？
の答えを見つける必要があります。
しかし、NP問題は無数にあり、それら全てに簡単に解くコツがあるのか調べるのはとても大変です。
P=NP問題の証明方法
実はP=NP問題を証明する方法は発見されています。
NP問題の中の一部の問題は「NP完全」と言われます。
ちなみに先ほど紹介したNP問題の例は全てNP完全です。
- 巡回セールスマン問題
- ナップサック問題
- ぷよぷよの連鎖問題
つまり、これら「NP完全」のNP問題を簡単に解くコツを1つでも見つけることができればP=NPであることを証明できます。
もしもP=NPが証明されたら
もしもP=NPであると証明されると世の中にどのような影響があるのでしょう？
今までしらみつぶしに調べていたものが簡単に解けるようになるので
- 研究開発のスピードUP(新薬が開発されるスピードUP)
- 運送業界が最高率で配達可能に(ネットショッピングの効率もUP)
- 会社の人員配置の最適解がわかる(色んな企業の業績UP)
などいいこと尽くめです。
反対にP≠NPであることが証明されると、これらをずっとしらみつぶしで調べないといけないことが決まってしまいます。
なぜ数学を学ばないといけないのか？数学ができるようになってどんなメリットがあるのか？そんな疑問を持つ人は多いと思います。そこで、数学が役に立つシーンを集めてみました。こんな人にオススメ なぜ数学を学[…]
問題の意味は中学生でも理解できるのに、世界中の数学者を悩ませいている。そんな未解決問題をまとめました。中には賞金をもらえるものもありますよ。こんな人にオススメ 数学の未解決問題を知りたい 数学で一攫千[…]