「P≠NP予想」について、数学が苦手な中学生でも分かるように説明してほしいです。

Wikipediaを見てもサッパリ訳が分からなくて（当然でしょうか＾＾；）、
比較的くだけた表現のニコニコ大百科(http://dic.nicovideo.jp/a/p%E2%89%A0np%E4%BA%88% …を見ても、２割３割くらいしか理解できませんでした。
よろしくお願い致します。

No.1 回答者： stomachman 回答日時： 2015/04/29 07:47

P時間ということ：

　なんかの問題を解くプログラムを考えます。このプログラムに入力するデータのサイズをxとします。答が出るまでに掛かる時間はxによって異なる訳ですが、時間が大体 x^n (nは定数) に従って増えるのがP(polynomial, 多項式)時間ってことです。たとえば、筆算でx桁の数とx桁の数をかけ算すると、各桁について１桁同士のかけ算の処理をやる回数がx^2回あるわけで（定数倍は無視）、ってことはx^2(xの２乗)ぐらいの時間が掛かる。なので桁数xが倍になれば4倍の時間が掛かる。こういうのがpolynimialです。要するに「問題の規模が大きくなっても、手間はそれほど強烈に多くなる訳じゃない」ってことです。ま、nが100とかだったら実際問題かなり強烈ですけど、それでも、後述する”E時間”に比べれば屁のようなもんです。

NP時間ということ：
　「x個の質問に対してYesかNoを答えなくてはならない。ただし、考えたってわかんない質問をされるんで、デタラメに答えるしかない。合格するには全問正解する必要があります。そして、x個の質問に全部回答し終わった時点で、合格か不合格かだけを知らされます。何回やりなおしチャレンジをしてもよろしい。」という問題を考えます。
　すると、質問ごとにYesと答えた場合とNoと答えた場合の2通りがあるから、全体としてはYes/Noの選択のパターン(Yes/Noの選び方)は2^x通りある。たとえばx=10なら1024通りです。それらを片っ端から試してみるしかないんで、2^xの時間が掛かりますね。こういうのがE(exponential, 指数関数)時間です。
　でも、この問題の場合、「デタラメにYes/Noを選んで答えたら、ナントまぐれで全問正解しちゃった」ということが起こりうる。逆に言えば、全問正解だというパターンが本当に合ってるのかどうかを確かめるためには、x個の質問に実際に答えてみて合格することを確認すれば良いだけ。だから、この確認作業はpolynimial時間でできる訳です。
　このことをさらに別の言い方で表せば、質問が出るたびに「分身の術」を使って「お前Yesと答えろ、俺Noと答える」とやれたとする。分身が次の質問を受けると、さらにまた分身を作る。分身が猛烈な勢いで増えちゃうわけですが、ともかく、こういう分身の術が使えるのなら、あらゆる「まぐれ」を同時に試す事ができるので、まぐれ当たりで全問正解のパターンを（沢山のうちのどれかひとつの分身が）発見するまでに掛かる時間はpolynomialである、ということになります。こういうのがNP(non-deterministic polynomial 非決定性多項式）時間。（「非決定性」という呼び名は、まさしく「もし分身の術が使えれば」ということを意味しています。）

P問題とNP問題：
　P時間で解く方法が分かっている問題をP問題と言います。
　NP時間で解ける（分身の術を使えばP時間で解けるという）方法なら知られているけれどもP時間で解くやり方が見つかっていないような問題がどっさりあって、これらをNP問題と言います。で、実は、多くの興味深い問題がNP問題なんです。（問題の分類はこれだけじゃありません。E時間でなら解けるがNP時間ではないようなE問題もあれば、解けないことが証明されている問題もありますし、そして解く方法があるのかないのか分かっていない問題もうんとこさある。）

NP完全とNP≠P：
　NP問題の中でも「NP完全問題」と分類される問題があります。NP完全問題とは、「もしその問題をP時間で解くやりかたが見つかったとすれば、そのやり方を応用することによって、あらゆるNP問題について、その解き方をP時間の解き方に変換できる」ということが証明された問題、という意味です。
　なので、NP完全問題のどれかひとつでも、それをP時間で解く方法を発見すれば、あらゆるNP問題はP問題になる。これが"NP=P"ということです。
　ですが現実には、長年かかっても、NP完全問題のどれについてもP時間で解く方法が見つからない。ってか、幾ら考えても無理っぽい。こりゃもう、「NP完全問題をP時間で解く方法はない」に違いない。これが"NP≠P予想"です。

そういうことなので：
　ならば、この予想を証明したい。ですが、これがとんでもない大難問なのです。「NP完全問題をP時間で解く方法はない」ということが、長年掛かっても証明できないんですよ。いろいろ工夫してみてもどうにもなんないんで、「もしかしてNP≠P予想は証明不可能な命題なんじゃなかろうか？」とまで考えられている。
　そう考えるんなら、じゃあ「NP≠P予想は証明不可能な命題である」という予想を証明したい訳ですが、いや、これも手が出ない。