P≠NP予想

P≠NP予想とは、不正確な表現を許すなら「難しい問題を簡単に解く方法は存在しない」という予想である。

概要

コンピュータは、実は1930年代に理論が完成している。現在もコンピュータの根幹を支え続けている数学的基礎付けは、アラン・チューリングというイギリスの数学者が作りあげたのだ。ここでは、その概略から始めてP≠NP予想に至るまでを述べよう。

コンピュータにとって、「難しい」問題とは何か？

ここで、但し書きをしておこう。

以下で扱う問題とは、「Yes」もしくは「No」の答えしか存在しない。

つまり、コンピュータがピコピコガーガーと動いた後、「はい」か「いいえ」しか言ってくれないのだ。そういう問題だけを取り扱うことにしよう。たとえば、「0011という文字列は、0と1の数が等しいか？」といった問題だ。「1から100までに素数は何個ある？」みたいな問題は取り扱わない。取り扱うなら、「1から100までの素数の数は10個以上である」みたいな問題に変換することにしよう。

さて、閑話休題。

コンピュータにとって、「難しい」問題とは、そのものズバリ解くのにめちゃくちゃ時間がかかる問題のことだ。たとえばあるアルゴリズムでは、一秒でサラッと答えを出せるのに対して、ほかのアルゴリズムでは十分、一時間かかるとする。つまり、「難しい」問題に対しては、「さらに速く」解けるアルゴリズムが、「カッコイイ」のだ。だってさ、総統閣下の演説に「ヤーーーッ！！」って即答するのがカッコイイでしょ？ 一時間も二時間もかかってから、ようやく「ヤーッ」って叫んでも、今頃おせぇんだよと突っ込み入れられること間違いなし。「難しい」問題に、華麗に即答するのがカッコイイアルゴリズムなのだ。

ただ、どれが難しくて、どれが易しいのかは、人間ではわからない。またどれだけ難しいかも、人間の判断基準とは異なる。なぜなら、アルゴリズムを適用するときには、コンピュータが主役になるからだ。「こんなの簡単じゃん！」ということさえ、コンピュータには難しいこともある。

そこで、「コンピュータとは何者ぞ？」という定義を行おう。それが、次に述べる「チューリングマシン」である。

チューリングマシンとは？

チューリングマシンとは、簡単に言えば入力列に対して結果を吐き出す、簡単なコンピュータのモデルだ。ただし、厳密には数学的に定義されている。

チューリングマシンの定義：

Kの要素は状態、Σの要素は入力記号、Γはテープ記号の有限集合、Fの要素は受理状態、sはKの要素のうち、初期状態とし、δはK×ΣからKへの写像であり、状態遷移関数とする。Bは空白記号とする。

チューリングマシン(TM) Mとは、K,Σ,Γ,δ,s,B,F として表される。ただし、Bを書き込むことはできない。

(KはQとする場合もある。また、sやFをq(init),q(acc)とする流儀もある。定義なので詳しくは教授に聞こう)

これだけでは何のことかさっぱりわからないかもしれないが、辛抱強く聞いてほしい。まず、次のようなモデルを考えてみよう。

問題：東京駅から大阪駅まで行けるか？(ただし、経路は問わないが、同じ駅は二度と通らないこととする)

このとき、Kの要素「状態」の初期位置、つまりsは「東京駅」である。

東京駅から大阪駅まで行きたいときには、どんな方法があるだろう。まず考えられるのは新幹線に乗ることだ。東京駅から新幹線に乗ったら、「新幹線乗車」という状態に遷移する。この「新幹線に乗る」という「遷移」を「状態遷移」という。あるいは、18きっぷを握りしめて東海道線に乗るかもしれない。これもまた状態遷移だ。

結局、新幹線とJRを使って大阪駅に到着するとする。ここでは、「東京駅から大阪駅まで行く」という問題を達成できたわけだ。この状態をF、つまり「受理状態」と呼ぶ。逆に、日本中を放浪してしまい、遙か彼方インドの奥地で力尽きてしまったとする。これは「不受理」として処理される。

このように、チューリングマシンとは、問題が与えられ、それをウームウームと解いていく一種の機械と考えることができるのだ（そして驚くべきことに、現在のコンピュータはすべて、1930年代に生み出されたチューリングマシンと同じ考え方で構成されている！）

もっと数学的なアルゴリズム論では、問題はたとえば次のように構成される。

問題：00001111は、0と1の数が同じか？

これを解くチューリングマシンを考えるのはたやすい。「0の数だけカウントを1UPさせて、1に出会うとカウントをダウンさせる」というチューリングマシンを作ればよい。最後にカウントが0になっていたら、受理だ。逆に、問題が「0111は、0と1の数が同じか？」という問題を、さきのチューリングマシンに解かせると、不受理となる。

アルゴリズムが「作れない」問題？

アルゴリズムは、すべての問題について手続きを与えてくれるわけではない。これを「非可解」な問題と呼ぶ。

ところで、皆さんは「いつまでも動画の読み込みが終わらない……」と悩んだことはないだろうか？ 動画はデータがたかだか有限なので、いつか待っていればなんとか100%読み込めるはずだ(ブラウザのバグとかは抜きにして)。ところが、「本当にいつまでたっても解けるかどうかわからない」という問題がある。これを「非可解」と呼ぶ。

非可解の問題で一番有名なのは、チューリングマシンの停止問題だ。

問題：チューリングマシンは入力に対して停止するか？

つまり、何らかの入力が与えられたとき、チューリングマシンの動作が本当に止まるかどうか？ というのは、非可解、つまりわからないのだ。

この手の問題にはアルゴリズムを作ることはできない。いつまでたっても、結局答えは出るかどうかわからないのだ。

再び：コンピュータにとって「難しい」問題とは？

では、最初に戻ってコンピュータにとって難しい問題とは何かを考えてみよう。

コンピュータは先に述べたように、チューリングマシンで模倣できる。現在使われているコンピュータは、まだ理論段階である量子コンピュータなんぞを除けば、すべてチューリングマシンの模倣だ。

だから、「難しい」問題のなかでも、頂点にいるのが「非可解」な問題なのだ。

じゃあ、非可解な問題を除いていけば、すべて可解なんじゃないか？ つまり、非可解問題を除けば、コンピュータさんは何でも答えを出してくれるよね！ という期待が当然わくことだろう。

本当にそうだろうか？

ネタバレをすると、解けます。でも……。

「難しい問題」を解くアルゴリズム

さて、ここまで読み進めていただいたなら、もう次の問題はすんなりわかるだろう。

問題：東京駅から大阪駅まで行けるか？(ただし、経路は問わないが、同じ駅は二度と通らないこととする)

これを計算機に解かせてみよう。可解かどうかはすぐにわかるはずだ。経路は問わないとはいえ、車、飛行機、まあ何にせよ有限個の経路しかない。あるいはそういう風に制限をつけてもいいだろう。「鉄道を利用することにする」などなど。そうすれば、おのずとこの問題は、ごく直感的に「解けそうだな」という気分がする。

では、実際に解いてみよう。

まず入力は、東京駅から出ているすべての路線だ。山手線、京浜東北線、京葉線、中央線、東北新幹線、東海道新幹線、etc……全部だ。そして、大阪駅からも多数の路線が出ている。東海道線、環状線、私鉄なども含めればさらに膨大になる。

この問題を、コンピュータに解かせると、次のようになる。

「えーっと、東京駅からは、山手線に乗ってみよう」
「おや、上野駅に着いたぞ。新幹線にも乗れるのか。東北に行ってみようかなぁ、それとも山手線に乗ったままにしようかなぁ……」
……
「稚内に来てしまった。同じ路線はもう使えないから飛行機に乗るしかないなぁ」
……
「ここはどこだ？」(北極で震えながら) →不受理

もうおわかりのように、コンピュータにとっては、大阪まで行き着こうと思うと総当たりで調べるしかないのだ。

方法が総当たりしかないというのは、コンピュータにとって、非常に難しい問題である。なぜなら、答えが出るまでずーーーっと待たなければならないからだ。ただし、「非可解」ではないので、何年かずーーーっとパソコンを動かしていれば答えが出るだろう。

しかし、「総当たりで調べる」というのも立派なアルゴリズムだ。逆に言えば、総当たりしかそれまで方法がないと思われていたアルゴリズムに、もっとうまいやり方を考えるというのがアルゴリズムの研究である。「難しい問題を易しく解く」と言い換えた方がいいだろうか。

このように、「コンピュータに解かせるには難しすぎるアルゴリズムしかない問題」のことをNP問題という。

もっと厳密に言えば、非決定性チューリングマシンによって(多項式時間で)解ける問題のことをNP問題という。

決定性・非決定性ってなーに？

それは難しい問題だ(人間にとって)。

ごくおおざっぱに言えば、東京駅で、「中央線に乗ろうかな〜それとも山手線に乗ろうかな〜新幹線もいいな〜」とフラフラ迷ってるヤツがいたら、そいつは「非決定性」だ。非決定性なヤツは、次の行動のバリエーションがたくさんあって、東京駅からどこか遠くに行ってしまう可能性がある。逆に、「東京駅からは新幹線にしか乗りません(ｷﾘｯ」というヤツは「決定性」という。決定性のチューリングマシンなら、「東京駅」というデータが送られたらすぐさま新幹線に乗るのだが、非決定性チューリングマシンはもしかしたら中央線に乗っているかもしれない。

人間にとっては理解しがたいかもしれないが、コンピュータにとっては、膨大な路線の網で、東京から大阪へ、しかも同じ駅を二度以上通らずに行くルートが果たしてあるかどうかというのは、非常に時間を要する問題なのだ。たまたま新幹線に乗れたとしても、新大阪で新快速に乗って寝過ごすという行動もあり得る。なんせ非決定性だから、運良く新大阪で降りられても、次の行動はさまざまなのだ。そういう場合、答えを出すにはさらに時間がかかるだろう。

つまり、非決定性チューリングマシンというのはマヌケなのだ。次の行動が決まっていない。だから東京駅から大阪駅まで行くのに、わざわざ東北新幹線に乗るというトンチキな行動を犯したりもする。そうして間違えながら、総当たりしまくって、よーーーーやく、大阪にたどり着いて「いやぁ答えをようやく見つけましたよ」と言ってきたりする。そこで、「仕方ないなぁ、答えを見つけたんだから他の場所にフラフラしててかかった時間は見逃してやるよ」と言ってやる。これがNP問題の定義である。

さらに詳しい定義：

ある問題が非決定性多項式時間限定チューリングマシンで解けるとき、その問題をクラスNPに入る(NP問題)と呼ぶ。

非決定性なので、ある様相(たとえば東京駅)から次の様相への遷移(新幹線に乗るとか、中央線に乗るとか)は複数存在してもかまわない。非決定的選択(フラフラ浮気しながらいろんなところに行く)を行って、初めて受理様相に達したとき、受理様相から初期状態への距離がO(n^k)で押さえられる(結果的に見ると、東京から大阪まではちゃんと行けましたね、ということが簡単に確認できる)。

このとき、東京から大阪にたどり着くまでに倒れちゃったとか、東京から大阪までアメリカ経由で行きましたとか、そういう他のルートにかかった時間は不問とする。

しかし、まあ、だいたい東京から大阪に行けと言ってるのにインドに行くようなヤツは信用ならないから、我々は総当たりで必死にルートを探すわけだ。それはいったい何年かかるかわからないけれど、まあ、いずれは答えを出してくれる。だから非可解ではないけれども、時間がかかるという意味で、超難しい問題には変わりない。

ところで、決定性チューリングマシンで多項式時間で解ける問題を、P問題という。状態に対して行動が一意的に定まっているマジメ君の解ける問題だ。マジメ君は、たとえば、「000111は0と1の数が同じか？」という問題で、0を数えてる途中に浮気して1を数え始めたりしない。

我々は、マジメ君しか信用したくないので、できれば浮気者の非決定性チューリングマシンでしか解けない問題を、なんとかマジメ君に解いてもらおうとして努力している。つまり、非決定性チューリングマシンで解くような問題を、マジメ君は総当たりを必死に始めるので、それがいたたまれないのだ。当然、マジメ君にもっと簡単に解いてもらう方法があるんじゃないだろうか？ という疑問がわき上がってくる。

NP≠P？

マジメ君が必死に総当たりを始める中、だんだんNP問題の数が増えてきた。これはマジメ君には荷が重いなぁ、どうにかしてマジメ君の計算量を減らしてやれないかなぁとみんな必死で考えていたのだ。

で、ある日、Steve Cookという人物は、「じゃあNP問題の中で、一番難しいヤツを探してやんよ！」と言って、NP完全という概念を生み出した。「この問題が解けちゃったら、ほかのNP問題もスゲー簡単に解けちゃうんだぜ！」という問題を探そうとしたのだ。

具体的には、問題QがNP完全——つまり最強に難しい問題——であるとき、問題Qが簡単に解けてしまうアルゴリズムが見つかった(これを具体的には決定性チューリングマシンで解ける、P問題という)ならば、ほかのあらゆるNPの問題は簡単に解ける(P問題になる)という問題だ。

そして確かに、そういう問題は見つかった。が、一個見つかったが最後、芋づる式に大量にNP完全な問題が出てきてしまった。あのぷよぷよや、テトリスさえも、NP完全であることがバレてしまったのだ。最強の問題がゴロゴロしていて、最近では見つかっても「あっそ」扱いされるレベルなのだ。

NP問題でググってここにくるかもしれない人に付け加えておくと、NP問題の検算は簡単だ。上の例のように、東京駅から大阪駅まで行くルートを見て、ちゃんとルールを破らずに一筆書きでやってきたかどうかをチェックするのは簡単である。これは決定性チューリングマシンで解ける、つまりP問題である。検算がP問題になるというのもNP問題の定義なので、P問題は実はNP問題に含まれる(これ以上はややこしいので、もっと知りたい人は大学に行くように)。

一般にNP問題を解くアルゴリズムの研究は、非常に難しいとされている。P問題はキッチリ計算できるのに、NP問題は解くためにかかる時間が非常に大きい。もし、NP問題がP問題のように、語弊を恐れず言うと「簡単に」解けるようなことがあれば、先に述べたように全世界が震撼する。が、やっぱり無理なんじゃねーの、というのが大方の見解だ。なぜなら、多くの数学者や計算機科学者たちが挑み続けているにもかかわらず、ずーっとNP完全な問題が簡単に解けるようなアルゴリズムは見つかっていないからだ。だから、みんなNPはPとイコールではないと思っている。これをP≠NP予想といい、新たな光明を見いだせたなら、あなたにはクレイ数学研究所から百万ドルがもれなくもらえる予定だ。

関連動画

関連項目

• コンピューター
• チューリングマシン
• アルゴリズム
• 暗号