P≠NP問題とは?確かめる易しさと見つける難しさをわかりやすく解説

なぜP≠NP問題は半世紀も解けないのか 未分類

日々の業務で、配送ルートの決定やシフト表の作成、限られた予算の配分といった「組み合わせの計画」に頭を悩ませた経験はないでしょうか。

選択肢が少し増えただけで急に決めきれなくなる現象の背後には、計算機科学で最も有名な未解決問題である「P≠NP問題(P対NP問題)」が深く関わっています。

本記事では、「P≠NP問題とは何か」という基本の問いから、PとNPの意味、そして計算の手間が爆発的に増える「多項式時間」と「指数時間」の違いまでを、数式をほとんど使わずに整理して解説します。

後半では、手元の仕事の問題が総当たりで解ける規模なのかを見積もる具体的な手順も確認していきます。

P≠NP問題とは?「確かめる易しさ」と「見つける易しさ」の違い

一文で言うと何を問う問題か

P≠NP問題を一文で言うなら、こうなります。

答えが正しいかどうかを素早く確かめられる問題は、答えそのものも素早く見つけられるのか。

懸賞を出しているクレイ数学研究所も、問題の紹介ページの冒頭でほぼ同じ言い方をしています。

解が正しいことを確かめるのが易しいなら、その問題を解くのも易しいのか、という問いです。

この問いには、まだ誰も証明つきの答えを出していません。

多くの研究者は「確かめるのは易しくても、見つけるのは本質的に難しい問題がある」と考えています。

それが「P は NP と等しくない」、つまり P≠NP という予想です。

題名に「≠」が入っているのは、この大多数の見方を反映した呼び方だからです。

英語圏では等しいかどうかを中立に問う「P 対 NP」という呼び方が一般的で、日本語でも「P対NP問題」と書かれることがあります。

どれも同じ問題を指しています。

クレイ数学研究所の例 寮に入る100人を選ぶ

クレイ数学研究所は、この問題を説明するのに学生寮の例を使っています。

400人の学生が入寮を希望していて、部屋は100人分しかありません。

さらに学生部長から「この二人は同じ寮に入れてはいけない」という組み合わせの一覧を渡されます。

誰かが100人の名簿を作って持ってきたとしましょう。

その名簿が条件を満たしているかどうかは、すぐに確かめられます。

一覧にある組を一つずつ見て、両方が名簿に入っていないかを調べればよいからです。

紙と鉛筆でも、午後のうちに終わる作業です。

ところが、条件を満たす名簿を一から作るとなると話が変わります。

400人から100人を選ぶ選び方の総数は、研究所の説明によれば、既知の宇宙にある原子の数よりも多いのです。

一つずつ試す方法では、地球上のすべての計算機を何十億年動かしても終わりません。

確かめるのは易しい。

見つけるのは途方もなく難しく見える。

この差が本物なのか、それとも賢い方法がまだ見つかっていないだけなのか。

P≠NP問題が問うているのは、まさにこの点です。

P と NP は何の略か

P は「多項式時間」を表す英語の頭文字です。

多項式時間とは、入力の大きさが増えても、計算の手間がその大きさの何乗か程度にしか増えない、という意味です。

入力の大きさの2乗や3乗のように増えるなら、手間は大きくなっても手に負える範囲にとどまります。

P は、そのような手間で答えを出せる「はい・いいえで答える問題」を集めた集まりです。

NP は「非決定性の多項式時間」を表す略語です。

よく「多項式ではない」の略だと誤解されますが、そうではありません。

もともとは、分かれ道のたびに正しい方を当てられる架空の計算機なら多項式時間で解ける問題、という定義でした。

今では、同じ内容をもっと分かりやすく言い換えた定義が標準になっています。

クレイ数学研究所の公式問題文を書いたスティーブン・クックも、こちらの言い方を採っています。

答えが「はい」になるときには、それを示す短い証拠があり、その証拠が本物かどうかを多項式時間で検査できる。

そういう問題の集まりが NP です。

寮の例なら、条件を満たす100人の名簿が証拠に当たります。

P は NP に含まれる

定義から、P に入る問題はすべて NP にも入ります。

自分で素早く答えを出せる問題なら、証拠を受け取って確かめるのも素早くできるからです。

クックの問題文でも、この包含は「たやすく示せる」と書かれています。

したがって問われているのは、逆向きが成り立つかどうかです。

NP に入る問題、つまり確かめるのが易しい問題は、すべて P にも入るのか。

成り立つなら P と NP は同じ集まりになり、P=NP です。

一つでも P に入らない NP の問題があれば P≠NP です。

クックが挙げた二つの例

公式問題文には、ごく簡単な例が二つ載っています。

一つは「この数は平方数か」という問題です。

平方根を素早く近似する方法があるので、この問題は P に入ります。

もう一つは「この数は合成数か」、つまり1とそれ自身以外の約数をもつかという問題です。

約数を一つ見せてもらえば、割り算一回で確かめられます。

だから NP に入ります。

この問題は長いあいだ P に入るかどうか分かっていませんでしたが、2002年に効率のよい判定方法が見つかり、P に入ると分かりました。

この二つ目の例は、NP の問題が P に「昇格」することがあると教えてくれます。

ある問題を誰も素早く解けないからといって、それが P に入らないとは限りません。

だからこそ、すべての NP の問題について決着をつけるのは難しいのです。

数独で確かめる

もう一つ、身近な例で感覚を確かめておきましょう。

数独は、9行9列のます目に1から9の数字を、行・列・太枠の中で重ならないように入れるパズルです。

埋め終わった盤面を渡されたら、正しいかどうかは数分で確かめられます。

各行、各列、各枠に同じ数字がないかを見るだけです。

一方、空欄の多い盤面を解くのは、熟練者でも時間がかかることがあります。

ここで大切なのは、普通の9行9列の数独が難しいかどうかではない、という点です。

大きさが決まった問題は、どれほど時間がかかっても有限の手間で解けます。

P≠NP問題で問題にするのは、盤面を16行16列、25行25列と大きくしていったときに、解く手間がどう増えるかです。

確かめる手間は大きさに応じてゆるやかに増えますが、解く手間はこれまで知られているどの方法でも急激に増えます。

この「増え方」の違いを次の章で数字にします。

ここまでで、P≠NP問題が「正解を確かめる易しさ」と「正解を一から見つける易しさ」の違いをめぐる問いであることが見えてきました。

次に、この問いが単なるコンピュータの性能競争ではなく、なぜ半世紀以上も未解決の「数学の問題」とされているのか、そして「P対NP問題」に対してどのような誤解が生まれやすいのかを確認します。

P対NP問題が難しい理由・よくある誤解と実務への意味

この問題が「数学の問題」である理由

計算機の速さの話なら、技術が進めば解決するように思えるかもしれません。

けれども P≠NP問題は、計算機がどれだけ速くなっても変わらない「増え方」を問う問題です。

部品が千倍速くなっても、手間が入力の大きさに対して指数的に増えるなら、扱える大きさはわずかしか伸びません。

そのため、この問題に答えるには、ありとあらゆるアルゴリズムについて何かを言わなければなりません。

「この方法では遅い」と示すのは簡単ですが、「どんな方法でも遅い」と示すには、まだ誰も考えついていない方法まで含めて否定する必要があります。

これが、半世紀以上たっても答えが出ていない理由の核心です。

はい・いいえの問題に言い換える理由

P と NP は、どちらも「はい」か「いいえ」で答える問題の集まりとして定義されています。

けれども実務で知りたいのは、たいてい「いちばん短い配送ルートはどれか」「いちばん人件費の安いシフト表はどれか」といった、最もよいものを求める問題です。

これを最適化問題と呼びます。

二つの種類はうまくつながっています。

「総距離が100キロ以下のルートはあるか」という問いに素早く答えられる方法があれば、上限を90キロ、80キロと狭めながら何度も問い直すことで、最短の距離を絞り込めるわけです。

上限を半分ずつ動かせば、問い直す回数はそれほど増えません。

逆に、最短ルートを素早く求められるなら、その長さを100キロと比べるだけで「はい・いいえ」の問いにも答えられます。

つまり、最適化問題の難しさは、対応する「はい・いいえ」の問題の難しさとほぼ同じだと考えてかまいません。

よくある三つの誤解

一つ目の誤解は、NP を「難しい問題」の意味だと思うことです。

前に述べたとおり、NP は「確かめるのが易しい問題」の集まりで、その中には P に入る易しい問題もすべて含まれています。

二つ目の誤解は、P≠NP が正しければ、難しい問題は実際には解けない、と考えることです。

P≠NP が意味するのは、どんな入力に対してもいつも多項式時間で正しく答える方法はない、ということにすぎません。

入力の大部分に対して速く答えられる方法や、最適に近い答えを保証つきで出す方法、実際のデータで十分速い方法は、P≠NP と矛盾しません。

三つ目の誤解は、P=NP が示されたら、すぐに暗号が破られ、あらゆる計画問題が一瞬で解けるようになる、という見方です。

証明の中で使われる方法が、手間の増え方は多項式でも実際には巨大な時間を要するものかもしれません。

また、存在は示せても具体的な手順を与えない証明である可能性もあります。

呼び名がたくさんある理由

この問題には、日本語だけでも「P≠NP問題」「P対NP問題」「P=NP問題」といった呼び名があり、ドイツ語やスペイン語、ポーランド語、トルコ語などでも、それぞれの言葉で「P と NP の問題」と呼ばれています。

等号を使うか不等号を使うかで印象は変わりますが、問うている内容は一つです。

どちらの書き方を見かけても、同じ問いについて話していると考えてください。

実務の人にとっての意味

仕事の観点から見ると、P≠NP問題は「あなたの問題には、いつでも速く最適解を出す方法が、おそらく存在しない」という見通しを与えてくれます。

配送の順番、勤務表、詰め込み、時間割など、多くの計画問題がこの難しいグループに属しているからです。

悲観する必要はありません。

最悪の場合に速く解けないことと、実際のデータで十分よい答えが出せないことは別の話です。

理論が「いつでも最速は無理」と告げるからこそ、時間を区切る、近似で妥協する、問題を小さく分けるといった実務の工夫に意味が生まれます。

最初の章の要点は三つです。

P≠NP問題は「確かめる易しさ」と「見つける易しさ」が同じかを問うこと。

P と NP は計算の手間の増え方で定義される問題の集まりであること。

そして、すべての方法を否定しなければ P≠NP は示せないという点です。

次の章では、ここで何度も出てきた「易しい」「難しい」を、具体的な数字に置き換えます。

第1章の要点が整理できたところで、ここからは「易しい」「難しい」という感覚を具体的な数字に置き換えていきます。

計算の手間が入力の大きさに対してどのように増えるのかを見ると、いわゆる「P=NP」という式が何を表しているのかがはっきりと理解できます。

多項式時間と指数時間:P=NPの本当の意味と総当たりが破綻する理由

手間を「入力の大きさ」で測る

前の章では「易しい」「難しい」という言葉を、あえて感覚的に使いました。

ここからは、それを計算の手間の数え方に置き換えていきましょう。

ここが分かると、P≠NP問題の「式」が何を言っているのかが見えてきます。

計算の手間は、秒数ではなく、計算の基本的な手順を何回繰り返すかで数えるのが決まりです。

秒数は機械によって変わりますが、手順の回数は方法そのものの性質だからです。

そして、その回数が入力の大きさとともにどう増えるかに注目します。

入力の大きさとは、配送なら訪問先の数、シフト表なら従業員と日数の組の数、数独なら盤面のます目の数といった、問題の規模を表す数のことです。

たとえば、訪問先の一覧から最も遠い二地点を探すなら、すべての組を一度ずつ調べれば足ります。

訪問先が10か所なら組は45通り、100か所なら4,950通りです。

訪問先の数が10倍になると手間はおよそ100倍になりますが、増え方は「2乗」の範囲にとどまっています。

このように、手間が入力の大きさの何乗かで抑えられることを、多項式時間で解けると言います。

増え方を表で比べる

言葉だけでは差が伝わりにくいので、増え方を表で並べてみます。

数字は、入力の大きさに対して必要な手順の回数を計算したものです。

入力の大きさ 2乗で増える方法 3乗で増える方法 2倍ずつ増える方法
10 100回 1,000回 1,024回
20 400回 8,000回 約105万回
30 900回 27,000回 約10.7億回
50 2,500回 125,000回 約1,126兆回
100 1万回 100万回 約1.27掛ける10の30乗回

入力の大きさが10のときは、三つの方法に大きな差はありません。

2倍ずつ増える方法、つまり入力が1増えるたびに手間が2倍になる指数的な方法も、千回程度で済みます。

ところが大きさが50になると、2乗の方法が2,500回で済むのに対し、指数的な方法は千兆回を超えます。

仮に1秒間に10億回の手順をこなせる計算機を使うとしましょう。

大きさ50の指数的な方法には約13日かかります。

大きさ60なら約36年、大きさ100なら約40兆年です。

宇宙が始まってからの時間が約138億年と言われますから、比べものになりません。

計算機が千倍速くなったら

技術の進歩で計算機が千倍速くなったとします。

2乗で増える方法なら、同じ時間で扱える入力の大きさはおよそ31倍に広がります。

千の平方根が約31.6だからです。

3乗で増える方法でも、扱える大きさはおよそ10倍になります。

ところが2倍ずつ増える方法では、扱える大きさは10ほど増えるだけです。

2を10回掛けると1,024になり、千倍の速さはちょうどそれで使い切ってしまうからです。

訪問先50か所を一晩で処理できていたなら、千倍の機械でも60か所が限界になります。

この差は、P≠NP問題が計算機の性能の話ではないことをはっきり示しています。

手間が指数的に増える問題は、ハードウェアをいくら増強しても、扱える規模がほとんど伸びません。

逆に、多項式時間の方法が見つかれば、技術の進歩がそのまま扱える規模の拡大につながります。

巡回の総当たりはどれほど大きいか

実務に近い例として、配送車が営業所を出て何か所かを一度ずつ回り、営業所に戻る経路を考えます。

総当たりで最短を探すなら、回る順番をすべて試すことになります。

回る順番の数は、訪問先が増えるにつれて階乗で増えていくのが特徴です。

出発点を固定し、逆回りを同じものとみなすと、10か所なら18万1,440通りです。

15か所で約436億通り、20か所では約6京通りに達します。

1秒に10億通りを調べられても、20か所で約2年、25か所では約980万年かかります。

宅配の現場では、1台が1日に何十か所も回るのは珍しくありません。

総当たりが役に立たないのは明らかです。

「P=NP」という式の意味

検索すると「P 対 NP の方程式」「P=NP の公式」といった言葉がよく出てきます。

けれども P=NP は、何かの数を求める方程式ではありません。

P と NP という二つの問題の集まりが同じものかどうかを表す、集まりどうしの等号です。

第1章で見たように、P の問題はすべて NP に入っています。

ですから P=NP とは、NP に入る問題がもれなく P にも入る、という主張になります。

P≠NP とは、NP に入っていながら P に入らない問題が少なくとも一つある、という主張です。

どちらにしても、何かの値を代入して解く式ではない点に注意してください。

クックの公式問題文では、P は「多項式時間で動くチューリング機械が受け付ける言語の集まり」と書かれています。

チューリング機械とは、計算の手順を最も単純な形で表した理論上の計算機です。

言語とは、はい・いいえの問題を記号列の集まりとして表したものです。

厳密な書き方は専門書に任せますが、要点は「どんな問題を、どれくらいの手間で判定できるか」を、機械の種類に左右されない形で定めていることにあります。

入力の大きさが少し増えるだけで、指数時間の手間は宇宙の年齢すら超える規模に跳ね上がります。

一方で、理論上「多項式時間」と「指数時間」のどちらに分類されるかを見るだけでは見落としがちな点もあります。

ここからは、多項式時間と実務上の実用性との関係、時間とは別の物差しである記憶領域(PSPACE)、そして自分の業務問題の規模を見積もる手順を見ていきましょう。

記憶領域PSPACEと手元の問題の規模を見積もる方法

多項式時間が「どの機械でも同じ」である理由

多項式時間という物差しが便利なのは、計算機の作りに左右されにくいからです。

クックの問題文によれば、チューリング機械は、記憶装置を自由に読み書きできるような、より効率のよい計算機の模型を、手間を高々2乗か3乗にする程度で模倣できます。

ある機械で多項式時間で解ける問題は、別の普通の機械でも多項式時間で解けるということです。

2乗の2乗も、3乗の3乗も、やはり多項式だからです。

そのおかげで P という集まりは、表計算ソフトの中でもスマートフォンの中でも同じ意味をもちます。

多項式なら実用的とは限らない

ここで一つ、大事な留保があります。

多項式時間なら実用的だ、と言い切ることはできません。

クック自身が公式問題文で、入力の大きさの100乗の手順を要するプログラムは、大きさがたった10でも実行できないと述べています。

10の100乗回の手順は、宇宙のどんな計算機でも終わりません。

それでも研究者が多項式時間を「効率がよい」ことの目安にしているのは、自然な問題で多項式時間の方法が見つかると、たいていその後の改良で2乗や3乗程度まで手間が下がってきたという経験があるからです。

整数の計算、連立一次方程式、最短経路、二部グラフの組み合わせ、線形計画などは、その代表です。

逆の向きにも同じことが言えます。

指数時間で増える方法しか知られていない問題でも、実際のデータの多くは、うまく作られたソルバーで解けることがあります。

理論の物差しは、最悪の場合の増え方を測るためのもので、手元のデータが速く解けるかどうかを直接教えてくれるものではありません。

確かめる手間はどれくらいか

ここで、第1章の「確かめる易しさ」を同じ物差しで測っておきましょう。

20か所を回る経路を渡され、「総距離は100キロ以下か」と問われたとします。

確かめるには、隣り合う訪問先の距離を20回足し、100と比べれば終わりです。

手間は訪問先の数にほぼ比例して増えるだけです。

一方、そうした経路を探す側は、前の節で見たように約6京通りの候補を抱えています。

確かめる手間は20回程度、探す手間は総当たりなら京の単位です。

この落差が、NP に入る問題の典型的な姿です。

もし P=NP なら、この落差は見かけだけのもので、探す側にも多項式時間で済む賢い方法があることになります。

時間とは別の物差し 記憶領域

計算の手間には、時間のほかに記憶領域という物差しもあります。

計算の途中で、どれだけの量を覚えておく必要があるかを測るものです。

記憶領域が入力の大きさの多項式で抑えられる問題の集まりを PSPACE と呼びます。

時間と記憶領域の間には、分かっている関係とまだ分からない関係があります。

クックの公式問題文には、ごく小さな記憶領域で解ける問題の集まりから始めて、P、NP、PSPACE と順に大きくなる包含の列が示されているのです。

両端の集まりが違うことは簡単な議論で示せるのに、隣り合うどの二つについても、本当に違うのかを誰も証明できていません。

P≠NP問題は、この「分かっていない包含」の一つです。

言い換えると、計算の手間についての基本的な区別のかなりの部分が、いまだに証明できていないのです。

手元の問題の大きさを見積もる手順

ここまでの考え方を、自分の仕事に当てはめる手順にまとめておきます。

目的は、総当たりで済むのか、何か工夫が必要なのかを、作業の前に判断することです。

必要なものは、問題の規模を表す数と、選択肢の数え方だけです。

  1. 決めるべきものを一つずつ書き出します。たとえば「各配達先を何番目に回るか」「各従業員が各日にどの勤務につくか」です。
  2. それぞれの選択肢の数を数え、掛け合わせて全体の組み合わせの数を出します。従業員10人が30日それぞれ3種類の勤務から選ぶなら、3を300回掛けた数になります。
  3. 出てきた数を、1秒に10億通りという目安で割り、総当たりにかかる時間を見積もります。

3を300回掛けた数は、10の143乗を超えます。

小さな職場のひと月分のシフト表でさえ、総当たりの対象にはならないことが分かります。

こうした見積もりを一度でもしておくと、なぜ専用の道具が必要なのかを、社内で説明するときの材料にもなるでしょう。

P≠NP問題は、一見すると純粋な数学や理論計算機科学の話題に見えますが、「なぜ私たちの職場のシフト表や配送計画は手計算や総当たりで解けないのか」を根本から説明してくれる考え方です。

まずは手元の問題について、決めるべき項目と選択肢の数を掛け合わせ、総当たりでどれくらいの手間がかかるのかを一度見積もってみてください。

本記事は、完全版の一部を抜粋して構成したものです。

完全版では、本編の続きとして「NP完全とNP困難の違い」「クレイ数学研究所が定める百万ドルの懸賞規則と、AIや量子計算機をめぐる研究の現状」「ExcelのソルバーやOR-Tools、SciPy、Gurobiなど実務で使える最適化ツールの始め方と費用比較」までを一冊にまとめています。

理論の正確な見分け方から現場での具体的な道具選びまで体系的に押さえたい方は、完全版もあわせてご覧ください。

完全版は、note・Kindle・Google Play ブックス・Apple Books で各560円で販売しています。

コメント