これが解ければ億万長者？P＝NP問題とは
世の中には未解決問題というものがたくさんあります．
今回紹介するP＝NP問題は数学界の未解決問題の一つで100万ドル（約1.45億円）の懸賞金がかけられた問題です．この問題を解ければ，あなたも億万長者になれるかも？
前回，多項式時間アルゴリズムという最悪の場合，コンピューターでも解くことができない問題を紹介しました．
コンピューターは1秒間に100～1000億回以上の計算ができますが，そんな超絶優秀なコンピューターを持っても年単位，もしくは私たちが生きている間には計算が終わらないぐらい，計算量が爆発するということが起こります．
この計算量を調べたときに，多項式時間であれば最も時間がかかる場合でもなんとか現実的に解くことができますが，そうでなければ最悪，私たちが生きている間には問題が解けないことになってしまいます．
つまり，難しい問題というのはコンピューターが現実的に解くことができそうかどうかを示しており，超ざっくりいえば多項式時間で解けるか否かということを意味しているんですね．
今回のP，NP問題というのも同様に多項式アルゴリズムで解けるか否かで，問題を分別しています．
P，NPとは
冒頭にも述べたP=NP問題．
未解決問題としては聞いたことがある人もいるかもしれませんが，意外と勘違いされているようです．そもそもP, NP問題とは一体どんな問題なんでしょうか．
ここでは，普段絶対に目にすることのないP, NP問題について紹介していきます．
まずクラスPと呼ばれる問題はわかりやすく，”多項式時間内で解を求めることができる”問題という意味です．つまり，最悪な場合でもなんとかコンピューターを使って解けそうな問題ということですね．
それに対して，NPは逆に多項式時間ないで解けない問題かと思いきやそうではありません．これが最初のひっかけです．
クラスNPに分類される問題は，”解が与えられたとき多項式時間内で解の検証（yes or no）が判断できる”問題という意味だそうです．これだけ聞くと，一瞬，どういうこと？ってなりますよね．
もう少しかみ砕いて説明しましょう．
ここまで考えていた最適化問題というのは，「○○のときの最適な解は何ですか？」という問題になります．数学からは離れますが「あなたの好きな食べ物は何ですか？」といった，いわゆるオープンクエスチョンってやつですね．
それに対して，「○○のときの最適な解は選択肢Aですか？」という問題は，解が選択肢AかそうではないかのYesかNoで回答できるため，決定問題といわれます．「あなたはカレーが好きですか？」ときかれたら，YesかNoで答えますよね．
クラスNPの問題というのは，元の問題を決定問題に置き換えたときに，つまり元の問題に解（カレー）を与えて，それが正解（好き）ですか不正解（嫌い）ですか？と聞いたときに，正しく回答するのに多項式時間で解ける問題を指します．
「あなたの好きな食べ物は何ですか？」と聞かれて，即答できても悩みながらも死ぬまで答えを出せなくても，「あなたはカレーが好きですか？」と聞き直されて，好きか嫌いで答えられれば，クラスNP問題になります．
「あなたの好きな食べ物は何ですか？」という質問自体に回答できるかどうかは関係ありません．カレーが好きかどうかを死ぬまでに回答すればよいわけです．
なんだか不思議な感覚になるかもしれませんが，知らないと間違えそうなひっかけですよね．
P＝NP問題
P問題はそれ自体が多項式時間で解けるため，それを決定問題に置き換えても当然多項式時間で解くことができます．
「あなたの好きな食べ物は何ですか？」という質問に，カレーだとかラーメンだとか答えることができるのであれば（P問題），「あなたはカレーが好きですか？」という質問にも答えることができる（NP問題）はずです．
つまり，クラスPはクラスNPに含まれているといえます．
それでは逆はどうなるのでしょうか？
「あなたはカレーが好きですか？」という質問にも答えることができる（NP問題）の場合，「あなたの好きな食べ物は何ですか？」という質問に，答えられるのでしょうか？
死ぬまでに「カレーが好きだ」と答えるかもしれない（P=NP）ですが，悩みに悩んで死ぬまで答えがでない（P≠NP）とも考えられます．
もう少し数学的に言うと，NP問題はあくまで決定問題にしたときに多項式時間で解ける問題といっているだけで，NP問題だから多項式時間では解けないとは誰も言っていないのです．
NP問題の解き方はわからないが，もしかすると多項式時間で解けるのかもしれないし，本当に多項式問題では解けないのかもしれない，という状況になっているのが現状です．これがP＝NP問題です．
もし，あなたがNP問題は多項式時間では解けない（P≠NP）と証明するか，逆に，いやいや全てのNP問題は多項式時間解くことができるんだ（P＝NP）と証明するか，どちらかを達成したら1.4億円獲得することができます．
お金もすごいですが，それ以上に数学界に一生名を刻むことになるでしょう．
最後に
今回はP＝NP問題について紹介しました．私には絶対できませんが，読者の皆さんが数学に強い自信があったら是非挑戦して，歴史に名を刻んでみてください．
※加えて，今回のたとえはだいぶ魔改造しています．数学というのは抽象化され洗練された表現なので，それを現実の具体例に落とし込むのはなかなか難しく，語弊を与える可能性が高いです．あくまで雰囲気ぐらいのイメージで思っていただけたらと思いますし，もっといい比喩表現があればぜひとも教えていただきたいと思います．
最参考文献
この記事が参加している募集
この記事が気に入ったらサポートをしてみませんか？