PvsNP

P対NP問題をわかりやすく解説!解けたら1億円の未解決問題!

PvsNP

数学の未解決問題の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度ずつ訪問して戻ってくるとき、移動時間が最短になる経路を求める問題です。

PvsNP_1

訪問先の数を\(n\)としたとき、選択肢の総数は\(\displaystyle \frac{n!}{2n}\)通りになります。

訪問先が28件あったとすると

\(\displaystyle \frac{n!}{2n}=\frac{28!}{2×28}≒5.4×10^{27}\)
となります。
現代の最高スペックのスーパーコンピュータを使っても、これを計算するのに約274億年以上かかります。
宇宙ができて137億年なので、ちょうど2倍の時間になります。
たった28件でも計算できないとは驚きです。

ナップサック問題

ナップサックにいくつかの品物を詰め込むとき、総金額を最大にするパターンを求める問題です。

PvsNP_2

出展:wikipedia

品物には金額とサイズが与えられていて、ナップサックの容量以上に品物を詰め込むことはできません。

世の中に存在するお菓子を全て対象にされたりすると、とても難しいですね。

ぷよぷよの連鎖問題

実はパズルゲームのぷよぷよにもNP問題が存在しています。

「与えられたぷよで\(n\)連鎖以上可能か?」

この問題はしらみつぶしに調べないと答えを求めることができません。

簡単に解けないからEスポーツにもなったんでしょう。
スポンサーリンク

P問題とは?

P問題とは、多項式時間以内で解くことができるアルゴリズムが存在する問題のことです。

簡単に表現すると「NP問題のようだが、簡単に解くコツがある問題」となります。

具体的には以下の問題がP問題になります。

ケーニヒスベルクの問題(一筆書き問題)

Konigsberg_bridges

出展:wikipedia

1735年に天才数学者オイラーが証明した問題です。

どんな図形でも一筆書きできるかを簡単に判断することができます。

関連記事

実は一筆書き問題を簡単に解くコツが存在します。なんとこのコツを知っていれば、その図形が一筆書きが可能か判断でき、スタートとゴールの点もどこかわかってしまうのです。この記事では「一筆書き問題を簡単に解くコツ」から「コツが発見さ[…]

kelly-sikkema-2NPV75ItVhg-unsplash

素数判定問題

ある数\(n\)が素数かどうか?を確認するためには、\(n\)未満の素数全てで割り切れないことを確認する必要がありました。

しかし2002年にAKS素数判定法が発見されました。

AKS素数判定法を使えば、\(n\)が素数かどうかを判定することができます。

AKS素数判定法

判定対象の数を\(n\)とする。

  1. \(n=a^b\)であれば\(n\)は素数ではない。(\(a,b\)は自然数、\(b>1\))
  2. \(o_r(n)>\log^2n\)となるような最小の数\(r\)を求める。
    \(o_r(n)\)は\(n^e\equiv1(\mod r )\)を満たす\(e\)を指す。
  3. \(a≤r\)となる\(a\)のいずれかが\(1<(a,n)<n\)を満たす場合、\(n\)は素数ではない。
    (\(a,n\))は\(a\)と\(n\)の最大公約数である。
  4. \(n≤r\)ならば\(n\)は素数である。
  5. \(1≤a≤[\sqrt{φ(r)} \log{n}]\)の範囲\(a\)に対して\((X+a)^n≢X^n+a(\mod X^r-1,n )\)ならば\(n\)は素数ではない。
  6. \(n\)は素数。
しらみつぶしに調べる必要がなくなったので、素数判定問題はP問題になりました。
スポンサーリンク

P対NP問題の解き方

P対NP問題は

  • P=NPなのか?
  • P≠NPなのか?

を問われている問題です。

つまり

  • 全てのNP問題には簡単に解くコツがあるのか?
  • 簡単に解くコツがなく、しらみつぶしに調べるしかない問題が存在するのか?

の答えを見つける必要があります。

しかし、NP問題は無数にあり、それら全てに簡単に解くコツがあるのか調べるのはとても大変です。

P対NP問題を解くことがNP問題のように感じられますね。
また、あるNP問題に簡単に解くコツが存在しないことを証明するのもとても大変です。
幽霊が存在しないことを証明するのと一緒ですね。

P=NP問題の証明方法

実はP=NP問題を証明する方法は発見されています。

NP完全であるNP問題の1つがPの場合、P=NPとなる。

NP問題の中の一部の問題は「NP完全」と言われます。

ちなみに先ほど紹介したNP問題の例は全てNP完全です。

  • 巡回セールスマン問題
  • ナップサック問題
  • ぷよぷよの連鎖問題

つまり、これら「NP完全」のNP問題を簡単に解くコツを1つでも見つけることができればP=NPであることを証明できます。

さらに1億円もあなたのものです。
しかし残念ながら多くの数学者はP≠NPであると予想しています。
スポンサーリンク

もしもP=NPが証明されたら

もしもP=NPであると証明されると世の中にどのような影響があるのでしょう?

今までしらみつぶしに調べていたものが簡単に解けるようになるので

  • 研究開発のスピードUP(新薬が開発されるスピードUP)
  • 運送業界が最高率で配達可能に(ネットショッピングの効率もUP)
  • 会社の人員配置の最適解がわかる(色んな企業の業績UP)

などいいこと尽くめです。

反対にP≠NPであることが証明されると、これらをずっとしらみつぶしで調べないといけないことが決まってしまいます。

世の中のためにもP=NPであってほしいですね。
関連記事

なぜ数学を学ばないといけないのか?数学ができるようになってどんなメリットがあるのか?そんな疑問を持つ人は多いと思います。そこで、数学が役に立つシーンを集めてみました。こんな人にオススメ なぜ数学を学[…]

what_useful_summary
関連記事

問題の意味は中学生でも理解できるのに、世界中の数学者を悩ませいている。そんな未解決問題をまとめました。中には賞金をもらえるものもありますよ。こんな人にオススメ 数学の未解決問題を知りたい 数学で一攫千[…]

question-mark-gec3539fd6_1920

もっと数学を楽しみたい方へ!
こちらの記事がオススメです!

\夢中になれる本だけを紹介/
記事を読む

スポンサーリンク
PvsNP
naze数gakuの最新情報はTwitterで配信中!
>なぜ数学を学ぶのか?

なぜ数学を学ぶのか?

数学はとても面白いし役に立ちます。
それを少しでも多く伝えれば思っています。
このサイトでは筆者が「本当に面白い」と感じた内容だけを記載しています。