わかりやすく P対NP とは

場合の数が爆発する

ある人がいくつもの町を一回ずつ全部回って、いちばん短い道を見つけたいとしましょう。
町が三つなら、回る順番はいくつもありません。でも町を一つずつ増やしていくと、調べる順番の数はあっという間にとほうもなくなります。
下のボタンで町を増やしてみましょう。

町を増やすと、回る順番の数が爆発します。（町 +1 → 場合の数がかけ算で増える）

町が増えるたびに、順番の数はかけ算でふくらみます。ビッグオーで見た「爆発する増え方」がこれです。
町が十いくつになるだけで順番が多すぎて、一つずつ全部調べるやり方はすぐ行き詰まります。

解くのは難しいが、確かめるのは簡単

ところが、おもしろい点があります。答えを見つけるのは難しくても、だれかが答えを持ってくれば、それが正しいかを確かめるのはすぐです。
数独を思い浮かべてください。空欄を全部埋めるのは頭が痛いですが、埋め終わった盤がルールに合っているかを調べるのは、目でざっと見れば終わります。

答えの候補を押すと、確かめるのはすぐ終わります。（探すのは難しい · 調べるのはひと目）

見つけるのは難しく、確かめるのは簡単。この二つが別々に動くのが、こうした問題の特徴です。
巡回セールスマン問題も同じです。いちばん短い道を見つけるのは難しくても、「合計距離がいくら以下の道はあるか」と問うなら、だれかが出した道の距離を足してみるだけで確かめられます。

速い解き方はあるのか

ここで大きな問いが生まれます。「確かめるのが速い問題は、解くのも速いのだろうか」。
もしかすると、私たちがまだ賢い方法を見つけていないだけかもしれませんし、本当に速い解き方がないのかもしれません。
下で二つの立場を押してみましょう。

二つの立場を押してみます。（確かめるのが速い = 解くのも速い？ · まだだれも知らない）

驚いたことに、この問いの答えはまだだれも知りません。世界中の数学者や科学者が長いあいだ取り組んできましたが、「速い解き方がある」とも「ない」とも証明できていません。
これがコンピュータ科学でいちばん有名な未解決問題です。だから、だれかが「簡単だ」と言ったら、少し疑ってもかまいません。

難しい問題たち

こうした問題は一つだけではありません。いくつもの町をいちばん短く回る道、重さの上限の中でいちばん価値のある荷物を選ぶナップサック、隣の国どうしが同じ色にならないように地図を塗り分ける問題があります。
見た目はまったく違っても、中身は似ています。場合の数が爆発し、確かめるのは簡単だという点です。
下で例を切りかえてみましょう。

例を押して切りかえます。（巡回セールスマン · ナップサック · グラフの塗り分け、どれも同じ種類の難しさ）

こうして似た問題が、何千も集まっています。不思議なことに、このうち一つでも速く解く方法が見つかれば、残りもすべて速く解けます。
いわば手をつないでいるのです。一つ解けば全部解けるのだから、なおさらおもしろいのです。

まとめ

一行にまとめるとこうです。ある問題は、入力が少し大きくなるだけで場合の数が爆発するので、速い解き方がまだ知られていません。
でも、答えを見つけるのは難しくても、確かめるのは簡単なことが多いのです。では、確かめるのが速ければ解くのも速いのか。これはまだだれも知らない大きななぞです。
下で順に押してまとめましょう。

要点を順に押してまとめます。（爆発 → 確かめるのは簡単 → まだ未解決）

すべての問題が同じように簡単なわけではありません。本当に手ごわい問題もあります。
でも、手ごわいからといって終わりではありません。次のレッスンでは、完璧な答えをあきらめるかわりに、「十分によい答え」を速く見つける賢い方法に出会います。