情報科学最大の難問：P 対 NP 問題

とても難しく、しかも興味深いとされる7つの数学の問題があります。クレイ数学研究所はこれらをミレニアム懸賞問題とよび、どれか一つを解いた人には賞金100万ドルを贈ることにしています。そのうちの一つは情報科学にもかかわる問題で、P 対 NP 問題（P≠NP予想）とよばれています。この問題がいったい何についての問題なのかを説明しましょう。

正直にいうと、説明は簡単ではありません。なにしろミレニアム懸賞問題ですから。おいしい緑茶でもいれて 🍵、始めましょう。まず、情報科学とアルゴリズムの世界から4つの問題を紹介します。それぞれの問題を分析して、P や NP という文字とどんな関係があるかを見ていきます。

問題1：最小の数を見つける

P 対 NP 問題は、アルゴリズムとその計算量にかかわる問題です。目の前に100枚の紙切れがばらまかれていて、どの紙にも数が1つずつ書かれているとします。この中から、いちばん小さい数が書かれた紙を見つけてください。どれくらい時間がかかるでしょうか。

30秒でしょうか。2分でしょうか。

理論的な情報科学では、こうした時間の単位にはあまり興味がありません。むしろ興味があるのは操作の回数です。そこで、問いを少し変えてみましょう。いちばん小さい数を見つけたと確信するには、何枚の紙を調べる必要があるでしょうか。答えは「すべて」です。いちばん小さい数は最後の1枚に書かれているかもしれないからです。紙が100枚なら100枚、1,000枚なら1,000枚を調べなければなりません。一般に、紙が n 枚なら、n 枚を調べる必要があります。

これをアルゴリズムの計算量といいます。n 枚の紙からいちばん小さい数を見つけるのに n 回の操作が必要なとき、この最小の数を探すアルゴリズムの計算量は n です。計算量が1次関数で表されるので、これを線形の計算量ともいいます。

さて、100枚の紙を調べて、いちばん小さい数は17だと答えたとします。その答えが正しいことを、どうやって確かめればよいでしょうか。もう一度すべての紙を調べて、17より小さい数がどの紙にも書かれていないことを確かめるしか方法はありません。つまり、いちばん小さい数を見つけるには n 枚の紙を見る必要があり、それを確かめるときにも同じことをしなければなりません。結果を検証する計算量も n、つまり線形です。

では、結果を見つけるより、結果を確かめるほうが簡単なアルゴリズムはあるのでしょうか。

問題2：積がある値になるペア

今度は、同じ枚数の紙切れの山が2つあるとします。どの紙にも、やはり数が1つずつ書かれています。山 A から1つ、山 B から1つ数を選んで、その積が918になるようにしてください。例えば、次のような山を考えます。

$\begin{array}{rcl} A & = & {49, 11, 32, 54, 15} \\ B & = & {17, 64, 74, 61, 21} \end{array}$

積が918になる2つの数の組は、どうすれば見つけられるでしょうか。単純に、すべての可能性を試せばよいのです。全部でいくつあるでしょうか。けっこう多く、25通りあります。まず、山 A の最初の数、つまり49を、山 B のそれぞれの数とかけてみます。

$\begin{array}{rcl} 49 \cdot 17 & = & 833 \\ 49 \cdot 64 & = & 3136 \\ 49 \cdot 74 & = & 3626 \\ 49 \cdot 61 & = & 2989 \\ 49 \cdot 21 & = & 1029 \end{array}$

918になる組はありません。そこで、山 A の残りの数でも同じことをします。11について5組、32について5組、54について5組、最後に15について5組です。全部で25組の数を試すことになります。最終的に、54 · 17 = 918 であることがわかります。

このアルゴリズムの計算量はどうなるでしょうか。ここで考えるのは、何組の数をかけ算する必要があったかです。どちらの山にも5枚の紙があり、1つ目の山の5つの数それぞれを、2つ目の山の5つの数それぞれと組み合わせて試す必要がありました。全部で 5 · 5 = 25 通りを試したことになります。紙が10枚ずつの山なら、10 · 10 = 100 通りを試す必要があります。一般に、紙が n 枚ずつの山が2つあれば、n · n = n² 通りを試さなければなりません。

このアルゴリズムの計算量は n² です。2次関数で表されるので、2次の計算量ともいいます。

では、結果を確かめるのはどれくらい大変でしょうか。積が918になるのは54と17だという答えを聞いたら、答えた人のように2つの山のすべての組を調べ直す必要はありません。この1組 54 · 17 をかけ算するだけで、答えが正しいかどうかがわかります。つまり、この問題を解くには最大で n² 回のかけ算が必要ですが、検証するには1回のかけ算だけですみます。検証の計算量は定数で、1です。

この点で、計算そのものと、そのあとの検証に同じだけの手順が必要だった前の問題とは大きくちがいます。

また、この問題は前の問題よりけた違いに複雑です。1万枚の紙からいちばん小さい数を見つけるのなら、1日あれば見つけられるでしょう。しかし、1万枚ずつの山を2つ渡されて積を探すとなると、1万かける1万、つまり1億回のかけ算をしなければなりません。1秒に1回かけ算をしても、およそ3年かかります。

問題3：部分和問題

3つ目の問題を見てみましょう。今度は数が書かれた紙切れが12枚あり、その中から和が0になる紙を何枚か選んでください。枚数はいくつでもかまいません。例えば、次の数を考えます。

$A = {24, - 69, 1, - 15, - 76, - 60, 16, - 83, 48, - 22, 54, - 47}$

これらの数の中から、和が0になる数の組を選んでください。例えば、

$24 + 48 - 69 + 1$

の和は4なので、正しい答えではありません。正しい答えは……そうですね、宿題として自分で探してみてください 😉。和が0になる数の組は1つしかありません。この問題がどれだけ難しいかを実感できるはずです。

次に、この問題の計算量を考えます。この計算はそれほど簡単ではないので、どちらかというと興味がある人向けです。この問題の計算量の求め方を知りたい場合は、このまま読み進めてください。そうでなければ、次の節まで飛ばしてかまいません。⏩

和が0になる数の組は、どうすれば見つけられるでしょうか。数のすべての組合せを試すしかありません。2つの数の組、3つの数の組、4つ、5つ、…とすべて試し、それぞれの組について和が0になるかどうかを確かめます。そのような組合せはいくつあるでしょうか。

もっと小さい集合で考えてみましょう。3つの数の集合 B = {5, 7, 9} から、ちがう数の組、つまり部分集合はいくつつくれるでしょうか。全部で8つあります。

$\begin{array}{rcl} B_{1} & = & {} \\ B_{2} & = & {5} \\ B_{3} & = & {7} \\ B_{4} & = & {9} \\ B_{5} & = & {5, 9} \\ B_{6} & = & {5, 7} \\ B_{7} & = & {7, 9} \\ B_{8} & = & {5, 7, 9} \end{array}$

空集合 B₁ も数に入れていることに注意しましょう。今はあまり役に立ちませんが、念のため入れておきます。計算を簡単にするため、それぞれの部分集合に2進ベクトルを対応させます。2進ベクトルは、0と1を並べたもので、例えば00101010のようなものです。ここでは、長さ3の2進ベクトルを使います。ベクトル 101 は、「もとの集合の1番目と3番目の数を含み、2番目の数を含まない」部分集合、つまり集合 {5, 9} に対応させます。ベクトル 110 は、「もとの集合の1番目と2番目の数を含み、3番目の数を含まない」部分集合、つまり集合 {5, 7} に対応させます。ほかも同じようにします。

$\begin{array}{rcl} B_{1} = {} & \to & 000 \\ B_{2} = {5} & \to & 100 \\ B_{3} = {7} & \to & 010 \\ B_{4} = {9} & \to & 001 \\ B_{5} = {5, 9} & \to & 101 \\ B_{6} = {5, 7} & \to & 110 \\ B_{7} = {7, 9} & \to & 011 \\ B_{8} = {5, 7, 9} & \to & 111 \end{array}$

どの部分集合にも長さ3の2進ベクトルがただ1つ対応し、長さ3のどの2進ベクトルもただ1つの部分集合に対応することがわかります。そのため、長さ n のちがう2進ベクトルがいくつあるかを計算すれば、ちがう n 個の数からつくれる組合せの数がわかります。では、計算してみましょう。

長さ1の2進ベクトルは、0と1の2つです。

長さ2の2進ベクトルは、長さ1のすべての2進ベクトルの末尾に0をつけ加えると得られます。00と10です。もう一度、長さ1のすべてのベクトルの末尾に1をつけ加えると、01と11が得られます。これで、長さ2のすべてのベクトル00、01、10、11が得られました。

長さ3の2進ベクトルは、長さ2のすべての2進ベクトルの末尾に0をつけ加えた000、010、100、110と、1をつけ加えた001、011、101、111です。

長さが増えるごとに、同じように続けます。2進ベクトルの長さが1増えると、ちがう2進ベクトルの数は2倍になることがわかります。したがって、長さ4のベクトルでは、全部で 2 · 2 · 2 · 2、つまり 16 通りの組合せが得られます。

一般に、n 個の要素をもつ集合 M があるとき、集合 M のすべての部分集合の個数は、長さ n のちがう2進ベクトルの個数に等しく、次のようになります。

$\underset{n 個}{\underset{⏟}{2 \cdot 2 \cdot \dots \cdot 2}} = 2^{n}$

2ⁿ と n² は同じようなもの？ 🤷‍♂

このように、n 個の数の集合からつくれる部分集合は 2ⁿ 個あります。この例では n = 12 個の数があるので、2¹² 通り、つまり 4096 通りの組合せを調べる必要があります。この問題の計算量は 2ⁿ です。指数関数で表されるので、指数関数的な計算量ともいいます。

前の問題の計算量は n² でしたが、この問題の計算量は 2ⁿ です。よく似ていますね。しかし、指数が定数の場合と、指数が変数 n の場合とでは大きなちがいがあります。n = 4 のときは、次のようになります。

$\begin{array}{rclrc} n^{2} & = & 4^{2} & = & 16 \\ 2^{n} & = & 2^{4} & = & 16 \end{array}$

ここまでは同じです。では、n = 10 のときはどうでしょうか。

$\begin{array}{rclrc} n^{2} & = & 10^{2} & = & 100 \\ 2^{n} & = & 2^{10} & = & 1024 \end{array}$

おや、指数関数が一気に大きくなり、2次関数のおよそ10倍になりました。n = 20 のときはどうでしょうか。

$\begin{array}{rclrc} n^{2} & = & 20^{2} & = & 400 \\ 2^{n} & = & 2^{20} & = & 1 048 576 \end{array}$

n = 20 のとき、指数関数的な計算量は2次の計算量のおよそ2,600倍です。つまり、指数関数は2次関数よりずっと速く増加します。今度また、人々の間に指数関数的な速さで広がるパンデミックが起きたら、このことを思い出してください。

紙切れが20枚あれば、1,048,576 通りの組合せを調べなければなりません。これはかなりの数です。

結果が正しいことをどう検証するか

選んだ数の組の和が本当に0になることを検証するには、どれくらい時間がかかるでしょうか。これはかなり速くできます。その1組の数を足すだけです。和が0なら正しい紙の組を見つけたことになり、和が0でなければまちがった組を選んだことになります。

ここでも、結果を確かめるほうが、見つけるよりけた違いに簡単なことがわかります。

問題4：巡回セールスマン問題

巡回セールスマン問題は、もっとも有名なアルゴリズムの問題の一つです。大まかにいうと、品物を売り歩いているセールスマンがいるとします。このセールスマンは、生活費をかせぐためにたくさん旅をしなければなりません。そこで、日本の主要な14都市をすべて回ることにしました。むだをしたくないので、この14都市をすべて通るもっとも短い道順を見つけることにしました。その最短の道順を見つけるのが、ここでの課題です。

最短の道順はどうすれば見つけられるでしょうか。すべての可能性を試します。

問題を簡単にしましょう。どの2つの都市の間にも、最短の道がただ1つあるとします。すべての都市を回る最短の道順は、どうすれば見つけられるでしょうか。都市は14あります。そのため、出発する都市の選び方は14通りあります。例えば、札幌から出発したとしましょう。札幌からはどこへ行けるでしょうか。理論上は、ほかのどの都市にも行けます。つまり、残りの13都市から選べます。

この時点で、最初の2つの都市の回り方が全部で 14 · 13 通りあることがわかります。出発する都市の選び方が14通りあり、そのあと残りの13都市から選べるからです。

2つ目の都市に着いたら、さらに先へ進まなければなりません。すでに2つの都市に行ったので、残りの12都市のうちの1つへ向かいます。これで、最初の3つの都市の回り方は全部で 14 · 13 · 12 通りになります。

3つ目の都市に着いたら、残りの11都市から1つを選び、次に残りの10都市から1つを選び、と続けます。

すべての都市を回り終えるまでの選び方の総数は、次の積になります。

$14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

これを見て、「!」で表す階乗を思い浮かべた人もいるでしょう。この積は 14! に等しいといえます。

$14! = 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

つまり、14の都市をすべて通る道順は 14! 通りあります。これは多いでしょうか。かなり多いです。実際に計算すると、次のようになります。

$14! = 87 178 291 200.$

一般に、n 個の都市を回る最短の道順を探すには、n! 通りの道順を試す必要があります。この解き方の計算量は n! です。

正しい結果を見つけたことは、どうすれば検証できるでしょうか。最短の道順は福岡から札幌、次に大阪、…だと答えたとします。その答えが正しいことをどう確かめればよいでしょうか。これはかなり難しいのです 🤷‍♂。その道順を見ても、それが本当に最短かどうかを簡単に確かめる方法はありません。実は、計算全体をもう一度やり直さなければなりません。そのため、結果を検証する計算量も n! です。

クラス P と NP

4つの問題とそれを解くアルゴリズムを紹介し、解を見つけるのがどれくらい大変か、その解を確かめるのがどれくらい大変かを分析しました。まとめると、次の表のようになります。

問題	解く計算量	検証の計算量
最小の数	n	n
積がある値になるペア	n²	1
部分和問題	2ⁿ	n
巡回セールスマン問題	n!	n!

ここで、これらの問題を2つのグループに分けます。1つ目のグループは、解くのが簡単な問題です。計算量 n、n²、n³、n⁴ などで解ける問題です。n² のような式を多項式（英語で polynomial）とよぶので、この問題のクラスを文字 P で表します。つまり、クラス P は多項式時間で解ける（計算量が例えば n² や n⁷ である）問題を含みます。おおざっぱにいえば、ある程度簡単に解ける問題です。

したがって、クラス P には問題1の最小の数を見つける問題が入ります。解く計算量が n だからです。また、問題2の積がある値になるペアの問題も入ります。解く計算量が n² だからです。どちらも多項式です。

2つ目のクラスはクラス NP です。これは、多項式時間で検証できる問題を含みます。そのため、クラス NP には最後の問題以外のすべての問題が入ります。巡回セールスマン問題は多項式時間で検証できませんが、ほかの3つの問題は多項式時間で検証できます。

巡回セールスマン問題は、多項式時間で解くことも検証することもできません。そのため、巡回セールスマン問題には、もっと難しい問題を含む別のクラスが必要です。そのようなクラスはありますが、ここでは扱いません。

クラス P がクラス NP の部分集合であることは明らかです。つまり、クラス P に属するどの問題も、クラス NP にも属します。これは納得できるでしょう。ある問題を多項式時間で解くことができるなら、その結果を多項式時間で検証することもできるからです。

P 対 NP 問題

では、逆も成り立つでしょうか。クラス NP のどの問題も、クラス P にも属するのでしょうか。つまり、ある問題の結果を多項式時間で検証する方法があるなら、その問題を多項式時間で解くアルゴリズムもあるのでしょうか。

例えば、問題3の部分和問題の結果は、多項式時間で検証できることがわかっています。しかし、この問題を解くのに使ったアルゴリズムは多項式時間ではなく、計算量が 2ⁿ の指数関数的なアルゴリズムでした。では、この問題に多項式の計算量のアルゴリズムが存在しないことは確かなのでしょうか。

わかっていません。

多項式時間で検証できるどの問題にも、その問題を多項式時間で解くアルゴリズムが存在する、ということも十分ありえます。それはわかっていないのです。そのようなアルゴリズムの存在を証明することも、存在しないことを証明することもできていません。

もしクラス NP のどの問題にも、それを多項式時間で解くアルゴリズムがあるなら、クラス NP は実はクラス P と等しいことになります。クラス P のすべての問題がクラス NP に属し、クラス NP のすべての問題がクラス P に属することになり、2つのクラスは等しく、まったく同じものになります。

つまり、P 対 NP 問題とは、クラス P とクラス NP が等しいのか、それとも2つのちがう問題のクラスなのか、という問題です。

P = NP と P ≠ NP の、どちらか一方が成り立ちます。どちらなのかはだれも知りません。もし答えを見つけたら、賞金100万ドルと永遠の名声、そしておそらくチューリング賞も待っています。チューリング賞は、情報科学のノーベル賞のような賞です。

P = NP なら何が起こるか

もし P = NP が成り立つとしたら、何が起こるでしょうか。何が起こるかを答えるのは、それほど簡単ではありません。クラス NP のすべての問題に、それを多項式時間で解くアルゴリズムがあることがわかります。例えば、問題3の部分和問題にも、それを多項式時間で解くアルゴリズムがあることになります。ただし、これには3つの落とし穴があります。

そのようなアルゴリズムが存在するとわかっても、それを見つけられるとは限りません。多項式時間で問題を解くアルゴリズムが存在することはわかっても、それをつくれるようになるまで、さらに100年かかるかもしれません。一般相対性理論がブラックホールの存在を予言してから、ブラックホールの最初の「写真」を撮影できるまでに何十年もかかったのと似ています。
多項式時間で動くアルゴリズムが存在しても、残念ながらそれが速いとは限りません。計算量が n¹⁰⁰ のアルゴリズムが見つかるかもしれません。式 n¹⁰⁰ も多項式だからです。計算量 2ⁿ と n¹⁰⁰ をくらべると、n が比較的小さいうちは、計算量 2ⁿ のアルゴリズムのほうが必要な操作の回数が少ないことがわかります。例えば n = 20 のとき、2²⁰ = 1,048,576 ですが、式 20¹⁰⁰ はおよそ130けたの数になり、1,048,576よりけた数が120ほど多い数です。そのため、この多項式時間のアルゴリズムは、実際には指数関数的なアルゴリズムより遅くなります。少なくとも n が比較的小さいうちは、そうです。
もし多項式時間で動く速いアルゴリズムが本当に見つかれば、たくさんの問題をもっと速く、もっと正確に解けるようになります。これはもちろんよい知らせですが、悪い面もあります。ある種の問題が解きにくいことを前提にしている分野があり、それが暗号（暗号理論）です。今使われている暗号が、けた違いに簡単に破られるようになるかもしれません。

ひと休み：ここまで読んでくれたごほうびに、問題3の答えを教えましょう。答えは 24 + 1 − 60 + 16 − 83 + 48 + 54 です。

P ≠ NP なら何が起こるか

もしクラス P と NP がちがうクラスだとしても、それほど大きなことは起こりません。今の状態とほぼ同じだからです。現在、NP の難しい問題を多項式時間で解くアルゴリズムは一つも知られていません。もしだれかが P ≠ NP を証明したら、その状態がずっと続くことになるだけです。P = NP の証明のほうが、ずっと大きな衝撃になるでしょう。

大衆文化の中の P 対 NP 問題

『ザ・シンプソンズ』のあるエピソードでは、ホーマーがある別世界に入りこみ、そこで P = NP という式を目にします。youtube.comで見られます。
一方、『フューチュラマ』では、倉庫に P と NP という名前の2つの箱が置かれている場面があります。youtube.comで見られます。
ドラマ『エレメンタリーホームズ&ワトソン in NY』のシーズン2第2話（原題「Solve for X」）は、P 対 NP 問題をおそらく解いた数学者の殺人事件を扱っています。

« 前へ: 1 + 2 + 5 · 0はいくつ？　かけ算を先にする計算の順序

次へ: 指数時間仮説（ETH） »