2000年、クレイ数学研究所は「ミレニアム懸賞問題」として7つの未解決問題を発表し、各問題の解決者に100万ドルの賞金を懸けた。そのうちの1つが「P≠NP問題」だ。四半世紀が過ぎた今も未解決であり、コンピュータサイエンスにおける最大の謎であり続けている。
「解くのは難しいが、答え合わせは簡単」な問題
P≠NP問題を理解するには、まず「P」と「NP」の意味を知る必要がある。ジグソーパズルを例にしよう。1000ピースのジグソーパズルを完成させるのは大変だ。しかし、誰かが「完成した」と言って見せてきたとき、それが正しいか確認するのは一瞬でできる。箱の完成図と見比べればいい。
P≠NP問題は、この直感を数学的に問う。「答え合わせが素早くできる問題は、解くのも素早くできるのか？」——これがP≠NP問題の核心だ。
| クラス | 定義 | 具体例 |
|---|---|---|
| P（Polynomial） | 多項式時間で「解ける」問題 | ソート、最短経路、線形方程式 |
| NP（Nondeterministic Polynomial） | 多項式時間で「答えの正しさを検証できる」問題 | 巡回セールスマン問題、ナップサック問題、充足可能性問題 |
| NP完全（NP-Complete） | NPの中で「最も難しい」問題のグループ | 巡回セールスマン問題、3-SAT、グラフ彩色 |
| NP困難（NP-Hard） | NP完全以上に難しい問題 | 停止性問題、最適スケジューリング |
「多項式時間」とは、入力サイズnに対してn、n^2、n^3のように多項式で計算時間が表せること。これに対し「指数時間」は2^nやn!のように爆発的に増加する。n=100のとき、n^2=10,000だが、2^n=約1.27×10^30。宇宙の年齢を秒換算しても足りない桁数だ。
P=NPだったら何が起こるか
もしP=NP——つまり「答え合わせができる問題はすべて効率的に解ける」ことが証明されたら、世界は一変する。
| 分野 | P=NPの場合の影響 | 現在の前提 |
|---|---|---|
| 暗号技術 | RSA暗号、楕円曲線暗号が即座に解読可能に | 「素因数分解は困難」という前提で安全 |
| [創薬](/tag/drug-discovery) | タンパク質の最適な折り畳み構造を瞬時に計算 | 膨大な候補から試行錯誤で探索 |
| 物流 | 最適な配送ルートを完璧に計算 | ヒューリスティクスで近似解を探す |
| [AI](/category/ai) / 機械[学習](/tag/learning) | 最適なモデルパラメータを直接計算 | 勾配降下法で局所最適に収束 |
| 数学 | 数学の証明を自動生成できる | 人間の直感と[創造性](/tag/creativity)に依存 |
インターネットバンキングもブロックチェーンも、現在の暗号技術の安全性はすべて「特定の問題を効率的に解くアルゴリズムは存在しない（だろう）」という仮定に基づいている。P=NPが証明された瞬間、その仮定は崩れる。
[エンジニア](/tag/engineer)が日常で遭遇するNP完全問題
「NP完全問題なんて理論の世界の話でしょ」と思うかもしれないが、実はエンジニアの日常業務にも潜んでいる。
| 日常の問題 | 対応するNP完全問題 | 実務での対処法 |
|---|---|---|
| 会議室の割り当て | グラフ彩色問題 | 貪欲法でほぼ最適な割り当て |
| タスクのスケジューリング | ジョブスケジューリング問題 | 優先度ベースのヒューリスティクス |
| テストケースの最小化 | 集合被覆問題 | 貪欲法で近似解 |
| コンパイラの最適化 | レジスタ割り当て問題 | グラフ彩色の近似 |
| ネットワーク設計 | シュタイナー木問題 | 2近似アルゴリズム |
| データベースのクエリ最適化 | 結合順序最適化 | 動的計画法＋ヒューリスティクス |
ここで重要なのは「解けない」ではなく「最適解を保証して効率的に解けない」という点だ。実務では近似アルゴリズムやヒューリスティクスを使い、「十分に良い解」を高速に見つけるアプローチが主流だ。
なぜ25年間誰も解けないのか
P≠NP問題がこれほど難しい理由のひとつは、「解けないことを証明する」こと自体が途方もなく難しいからだ。P=NPを証明するなら、たった1つの効率的なアルゴリズムを見つければいい。しかしP≠NPを証明するには、「あらゆる可能なアルゴリズムの中に効率的なものが1つも存在しない」ことを示す必要がある。
多くの計算機科学者はP≠NPだと「信じて」いる。2019年の調査では、理論計算機科学者の88%がP≠NPだと予想した。しかし信じることと証明することの間には、果てしない距離がある。
もしこの問題が解けたら、100万ドルの賞金だけではなく、フィールズ賞やチューリング賞も確実だと言われている。しかしそれ以上に、コンピュータサイエンスの地図が根本から書き換わる。あなたが毎日書いているコードの「計算量」を気にするとき、その背景にはこの未解決問題が横たわっていることを、たまには思い出してみてほしい。
