数学の未解決問題シリーズ③「P≠NP予想」

このシリーズ、どこまで続けようかなぁ……。(笑)
っていうのも、中学生・高校生くらいが
理解できるような未解決問題を紹介していきたいんだけど、
手持ちのネタがあと２つ３つくらいしかないんだよなぁ……。(笑)
説明するのがあまりに難しいのは、
俺だって問題そのものの意味がわからないだろうし。(笑)


さてさて、今日の「P≠NP予想」は、
ちょっと今までのシリーズとは毛色が違うかも。
ちょっと論理学チックな予想なんだ。
まずはとりあえず、PとNPを説明しよう。


[Pの説明]
一言で書けば、
「Pに属する問題は、多項式時間(polynomial-time)で答えが出せる。」
っていうことかな？さらに思いっきり平たく書けば、
「一般的で簡単な解法が存在する問題はPに属する。」って事だ。
Pに属する問題の良い例の一つが、二次方程式かな？
今、って二次方程式を
解いてくれって言われたらどうする？
多分、みんな因数分解してを導き出すと思うんだ。
これは、まだ簡単に因数分解ができたけど
仮に因数分解のできないタイプの二次方程式を解けと言われても
という解の公式を利用すれば
簡単に答えを出すことはできるよね。
この解の公式は、一定の計算量しか必要にならないので
これが、「Pに属する問題」って事。


[NPの説明]
一方、「NPに属する問題」って端的に書けば
「一般的な解法が存在しない問題」っていうことだね。
例えば、こういう問題。

昼食を食べにマクドナルドに行った。メニューを見ると、

ハンバーガー	84円
チーズバーガー	126円
てりやきマックバーガー	199円
ダブルチーズバーガー	231円
ビッグマック	262円
ガーデンサラダ	252円
ホットアップルパイ	157円
ドナルドビスケット	105円
プチパンケーキ	178円

となっている。
さて、俺は今731円持っていて
この金額の全て(ピッタシ731円)を費やしていろんな物を食べたい。
さて、俺はこの731円ピッタリで
食べれるメニューの組み合わせは存在するのか？

さて、この問題の場合は、二次方程式みたいに
これといった一般的な解法があるわけじゃない。
よって、とりあえずしらみつぶし的に、
すべての組み合わせを探索していくしか方法がなさそうだよね。
今の問題規模なら、全ての組み合わせを探索しても
大した時間はかからないけど、
もしメニューの種類が10000種類とかになって
俺の手持ちのお金が1568423円とかになると、
とてもじゃないけどコンピュータ使っても、
ぴったりその金額になる組み合わせを
俺が生きている間に発見できるかどうかわからない。
NP(Nondeterministic Polynomial)問題ってのは、
今の問題のように、すごい規模が大きくても
しらみつぶしでしか解けなさそうな問題のことを言う。


ただ、もしかするとNP問題でも
「まだ上手い一般的な解法が見つからないだけで、
　そのうち上手い解法が見つかるかもしれない。」
と考える人がいるかもしれない。
一方で、
「いや、そもそもこの手の問題は、
　二次方程式とはまるで質の異なる問題で、
　上手い解法なんてあるわけないだろ！」
と考える人もいるだろう。
前者がP＝NP、後者がP≠NPってこと。
世界中の数学者達が、おそらくP≠NPと予想しているが
それを数学的に証明した人はまだ誰もいない。


ちなみに、このP≠NP予想もリーマン予想と同じで
クレイ数学研究所が賞金をかけている未解決問題である。
参考リンク