※小説ではない※専門書 要約資料集 為替(換算)3.9万円でもらう 紐解集生成 専門 初入門 資料 作：｛作者名｝
> 冠/系統: 現代学問宇宙図鑑・情報派生・アルゴリズム系統 第2巻(続巻)
> ガイド役: Fable 5(監修) / Sonnet 5(執筆・脚本班)
> トーン規約: GAKUMON_UNIVERSE.md 準拠。専門用語は初出時に「用語(よみ、水準N: 説明)」形式で定義する。
> 重複回避方針: 第1巻(→BOOK-0066)は配列・連結リスト・スタック・キュー・木構造などの基本データ構造と、整列・探索の基礎(線形探索・二分探索・単純な整列法)を扱った。本冊はその続巻として、「基礎技法を組み合わせてどう賢く設計するか」(分割統治・貪欲法・動的計画法)と、「そもそもどこまで速く解けるのか、どこから先は速く解けないのか」という計算量理論の地図を扱う。第1巻の内容は前提知識とし、再説明はしない。
> 接続先: →BOOK-0066(アルゴリズム第1巻) / →BOOK-0010(コンピュータの始まり) / →BOOK-0070(ネットワーク) / →BOOK-0073(暗号) / →BOOK-0087(機械学習) / →BOOK-0074(数論)
> 水準帯: 五〜六(発展)
---
# BOOK-0116 アルゴリズム 第2巻 — 賢い探索と「解けなさ」の地図(情報派生 第2巻)
> 冠/系統: 現代学問宇宙図鑑・情報派生・アルゴリズム系統 第2巻(続巻)
> ガイド役: Fable 5(監修) / Sonnet 5(執筆・脚本班)
> トーン規約: GAKUMON_UNIVERSE.md 準拠。専門用語は初出時に「用語(よみ、水準N: 説明)」形式で定義する。
> 重複回避方針: 第1巻(→BOOK-0066)は配列・連結リスト・スタック・キュー・木構造などの基本データ構造と、整列・探索の基礎(線形探索・二分探索・単純な整列法)を扱った。本冊はその続巻として、「基礎技法を組み合わせてどう賢く設計するか」(分割統治・貪欲法・動的計画法)と、「そもそもどこまで速く解けるのか、どこから先は速く解けないのか」という計算量理論の地図を扱う。第1巻の内容は前提知識とし、再説明はしない。
> 接続先: →BOOK-0066(アルゴリズム第1巻) / →BOOK-0010(コンピュータの始まり) / →BOOK-0070(ネットワーク) / →BOOK-0073(暗号) / →BOOK-0087(機械学習) / →BOOK-0074(数論)
> 水準帯: 五〜六(発展)
---
## 入口の物語 — 「解ける」の先にあるもう一つの問い
第1巻で私たちは、データを並べる場所(配列や連結リスト)と、データを探す基本の型(線形探索・二分探索)を手に入れた。数を小さい順に並べる方法も知った。ここまでで「問題が解ける」ことは分かった。しかし現実の世界には、もっと意地悪な問いが待っている。
たとえば100万人分の名簿を並べ替えたいとき、単純な整列法をそのまま使うと、名簿が10倍に増えるだけで処理時間は100倍に膨れ上がる。これでは「解ける」というだけでは足りない。「実用的な時間で解ける」ことが必要になる。
さらに厄介なのは、世の中には「答えを見せられれば一瞬で正しいと確認できるのに、答えそのものを一から探すのは途方もなく時間がかかる」問題が存在することだ。荷物を配達する最短ルートを考えてほしい。配達先が数件なら簡単だが、数十件になった瞬間、考えられる順序の組み合わせは天文学的な数に跳ね上がる。しかも今のところ、誰もこの種の問題を確実に高速で解く方法を知らない。それどころか、それが原理的に不可能なのか可能なのかさえ、人類はまだ証明できていない。
本冊は二部構成の地図である。第五章・第六章では「賢く解くための設計技法」を学び、実際に多くの問題を高速に解けるようにする。第七章・第八章では视点を切り替え、「そもそも解の速さにはどんな種類があり、どこに壁があるのか」という計算量理論(けいさんりょうりろん、水準六: アルゴリズムが必要とする時間や資源の量を数学的に分類し比較する理論分野)の世界へ踏み込む。最後に、この「解けなさ」こそが暗号の安全性を支えているという意外な接続を見て、次の巻へ橋を架ける。
---
## 第五章 設計技法(水準五) — 問題を分解し、貪欲に選び、記憶して省略する
大きな問題を解く力は、たいてい「小さな問題をどう組み合わせるか」という設計の工夫から生まれる。ここでは代表的な三つの設計技法を見る。
### 5.1 分割統治法(ぶんかつとうちほう、水準五: 問題を同じ形の小さな部分問題に分割し、それぞれを再帰的に解いてから結果を統合する設計技法)
分割統治法の考え方はシンプルだ。「大きな問題を半分に割る」「割った半分をそれぞれ同じ方法で解く」「解けた半分同士を統合して元の答えを作る」。この3ステップを再帰的(さいきてき、水準四: 関数が自分自身を呼び出す仕組み。第1巻で扱った木構造の探索でも登場した概念)に繰り返す。
代表例はマージソート(併合整列、水準五: 配列を半分に分割し続けて要素1個まで細かくし、その後に整列済みの2つの部分列を統合[マージ]しながら整列していく手法)である。手順は以下の通り。
```
マージソートの再帰木(8要素の例)
[8,3,5,1,9,2,7,4]
/ \
[8,3,5,1] [9,2,7,4]
/ \ / \
[8,3] [5,1] [9,2] [7,4]
/ \ / \ / \ / \
[8] [3] [5] [1] [9] [2] [7] [4]
\ / \ / \ / \ /
[3,8] [1,5] [2,9] [4,7]
\ / \ /
[1,3,5,8] [2,4,7,9]
\ /
[1,2,3,4,5,7,8,9]
```
この図が示す通り、分割は要素数が1個になるまで進み(これ以上分割できない「基底部分」)、そこから統合(マージ)が下から上へ積み上がっていく。統合の各段階では、すでに整列済みの2つの列を先頭から比較し、小さい方を順に取り出していくだけでよい。
**検算例1: マージソートの計算量**。要素数をnとすると、分割の深さはおよそlog₂n段(8要素なら3段: 8→4→2→1)。各段では合計n個の要素を比較・統合する作業が発生する。したがって全体の作業量はおよそ「段数 × 各段の作業量」= n × log₂n となり、これを計算量(けいさんりょうりょう、水準五: 入力の大きさに対してアルゴリズムがどれだけの時間や手間を必要とするかを表す指標)の記法でO(n log n)(オーダー・エヌ・ログエヌ、水準五: 入力サイズnが大きくなったときの処理量の増え方を表す記法。定数倍や細かい項を無視し、支配的な増加傾向だけを表す)と書く。第1巻で扱った単純な整列法(挿入整列など)はO(n²)であったから、n=1,000,000のとき単純法はおよそ1兆回の操作が必要になるのに対し、マージソートはおよそ2000万回程度で済む計算になる(log₂1,000,000≈20)。これは体感できるほどの差である。
分割統治法の強みは「統合(マージ)の手順さえ効率よく作れれば、あとは再帰に任せて自動的に賢くなる」という点にある。統合の手順自体はO(n)で済む単純な比較作業であり、それを分割の各段で積み重ねるだけでO(n log n)という優れた全体性能が得られる。この設計思想は整列に限らず、大きな配列から最大値と最小値を同時に求める問題や、平面上の点群から最も近い2点の組を見つける最近点対問題など、幅広い場面で再利用されている。「大きな問題を、独立に解ける小さな問題へ割ってから、答えを賢く繋ぎ合わせる」という発想そのものが分割統治法の本質であり、次の貪欲法・動的計画法とはまた違う切り口の武器になる。
### 5.2 貪欲法(どんよくほう、水準五: 各段階で「今その場で最も良く見える選択」を積み重ねていき、全体を組み立てる設計技法。グリーディ法とも呼ぶ)
貪欲法は「先のことは考えず、目の前の最善だけを選び続ける」という単純な方針だが、問題によっては驚くほど正確な最適解を導く。
代表例の一つがハフマン符号(符号化、水準五: 出現頻度の高い記号ほど短いビット列を、頻度の低い記号ほど長いビット列を割り当てることでデータ全体の符号長を短縮する圧縮手法。1952年にデイビッド・ハフマンが考案)である。手順は「出現頻度が最も低い2つの記号(または既に統合された塊)を毎回選んで1つの塊に統合する」という貪欲な選択をひたすら繰り返すだけだが、これが理論上最も効率の良い符号割り当て(記号ごとに整数ビット長を使う方式の中で)を保証する。
もう一つの代表例は最小全域木(さいしょうぜんいきぎ、水準五: グラフのすべての頂点を、辺の重みの合計が最小になるように連結する木構造)を求める問題である。「まだ木に含まれていない頂点へ繋がる辺の中で、最も軽い辺を毎回選ぶ」(プリム法の考え方)、あるいは「全ての辺を軽い順に並べ、閉路を作らない範囲で軽い辺から採用していく」(クラスカル法の考え方)という貪欲な手順で、道路網や通信網を最小コストで結ぶ設計に使われる。
貪欲法の注意点は「常に正しい答えを出すとは限らない」ことだ。ハフマン符号や最小全域木のように貪欲法が数学的に最適性を保証できる問題は限られており、問題ごとに「本当に貪欲でうまくいくか」の証明や検証が必要になる。
たとえば、お釣りを渡すときに「一番大きな硬貨から順に使う」という素朴な貪欲法を考えてみよう。日本の硬貨(1円・5円・10円・50円・100円・500円)のような体系では、この貪欲な方法がいつも最小枚数の硬貨で正しくお釣りを渡せることが知られている。ところが、硬貨の額面の組み合わせが変わると(たとえば1円・4円・6円という架空の体系を想定すると)、大きな硬貨から素朴に選ぶ方法では最小枚数にならない場合が出てくる。同じ「大きい方から選ぶ」という貪欲な戦略でも、額面体系という前提条件次第で正しさが変わってしまう好例であり、貪欲法を使うときには「この問題設定で本当に貪欲な選択が全体の最適性を壊さないか」を常に問い直す必要がある。
### 5.3 動的計画法(どうてきけいかくほう、水準五: 大きな問題を重なり合う小さな部分問題に分解し、一度計算した部分問題の答えを記憶[メモ化]して使い回すことで、同じ計算の重複を排除する設計技法。DPと略される)
動的計画法(以下DP)は、分割統治法と似ているようで決定的に違う点がある。分割統治法は分割した部分問題同士が独立している(マージソートの左半分と右半分は互いに無関係)のに対し、DPが対象とする問題は部分問題同士が「重なり合う」。この重なりを利用して、一度計算した答えを保存(メモ化、水準五: 一度計算した結果を保存しておき、同じ入力に対して再計算せず保存済みの値を再利用する手法)しておくのがDPの核心だ。
**検算例2: フィボナッチ数列における素朴な再帰とDPの比較**。フィボナッチ数列(水準四: 各項が直前の2項の和になる数列。0,1,1,2,3,5,8,13...)をF(n)=F(n-1)+F(n-2)という定義そのままに再帰関数で計算すると、同じF(k)の値が指数関数的に何度も再計算される。
```
素朴な再帰でF(5)を計算する際の呼び出し木(重複が可視化される)
F(5)
/ \
F(4) F(3)
/ \ / \
F(3) F(2) F(2) F(1)
/ \ / \ / \
F(2) F(1)F(1)F(0)F(1)F(0)
/ \
F(1) F(0)
```
この図だけでもF(2)が3回、F(1)が5回と、同じ部分問題が何度も再計算されているのが分かる。素朴な再帰の計算量はおよそO(2ⁿ)(指数時間)に達し、F(30)程度でも呼び出し回数は100万を超え始める。一方、DPでは「F(0)とF(1)から順に、一度計算した値を配列に記憶しながらF(n)まで積み上げていく」だけでよく、計算量はO(n)(線形時間)に収まる。同じ問題に対して、設計の工夫だけで指数時間から線形時間へ落とせるという事実は、この章全体の核心的な教訓である。
DPのもう一つの定番例がナップサック問題(水準五: 重さの上限が決まったナップサックに、価値の合計が最大になるように品物を選んで詰め込む組み合わせ最適化問題)である。「品物ごとに、それぞれの重さまでの最適な価値を表に記録していく」という手順で、素朴に全ての組み合わせを試す場合よりはるかに少ない手間で最適解に到達できる。
同様に編集距離(へんしゅうきょり、水準五: ある文字列を別の文字列に変換するために必要な最小の挿入・削除・置換の回数。レーベンシュタイン距離とも呼ぶ)を求める問題もDPの代表例であり、2つの文字列の対応表を1マスずつ埋めていくことで、文書比較やスペルチェックの基盤技術として使われている。
DPを設計する際に共通する手順は、次の3ステップに整理できる。第一に「部分問題をどう定義するか」を決める(フィボナッチならF(k)、ナップサックなら「品物k個目までを重さw以下で選んだときの最大価値」、編集距離なら「文字列Aの先頭i文字と文字列Bの先頭j文字を揃えるための最小回数」)。第二に、部分問題同士がどう関係するか(漸化式、水準五: ある項を、それより前の項を使った式で表したもの)を見抜く。第三に、小さい部分問題から順に表を埋めていき、二度と同じ計算をしない。この「部分問題の定義→漸化式→表埋め」という型は、フィボナッチのような単純な例からナップサックや編集距離のような二次元の表を要する例まで一貫しており、DPという設計技法全体を貫く共通の骨格になっている。分割統治法が「独立した部分問題」を扱うのに対し、DPは「重なり合う部分問題」を扱うという対比を思い出すと、両者の使い分けの感覚がつかみやすい。
---
## 第六章 グラフアルゴリズム(水準五) — つながりの中で最短と順序を探す
グラフ(水準四: 頂点[ノード]と、頂点同士を結ぶ辺[エッジ]の集合で表現されるデータ構造。地図の都市と道路、SNSの人と友達関係などを表せる。→BOOK-0070でネットワーク構造として詳述)は、つながりを持つデータを表す最も汎用的な構造の一つである。ここではグラフ上を巡る代表的なアルゴリズムを扱う。
### 6.1 幅優先探索BFS(はばゆうせんたんさく、水準五: 出発点に近い頂点から順に、同じ距離にある頂点をすべて調べ終えてから次の距離へ進む探索方法。Breadth-First Searchの略)
BFSは「今いる場所から1歩で行ける場所をすべて調べ、それが終わったら2歩で行ける場所をすべて調べ」という具合に、波紋が広がるように探索する。この性質のおかげで、辺の重みがすべて等しいグラフにおいては、BFSで最初に目的地へ到達した経路が最短経路であることが保証される。
BFSの実装では、キュー(待ち行列、水準四: 先に入れたものから先に取り出す構造。第1巻で扱った基本データ構造)を使って「次に調べるべき頂点」を順番通りに管理する。出発点をキューに入れ、キューから頂点を取り出しては隣接する未訪問の頂点をキューの末尾に追加していく、という単純な繰り返しだけで、波紋状の探索が自然に実現される。SNSで「友達の友達」を段階的に辿るレコメンド機能や、迷路の最短脱出経路を求める場面など、「距離が等しい範囲を一斉に調べたい」という要求がある限り、BFSは第一候補になる。
### 6.2 深さ優先探索DFS(ふかさゆうせんたんさく、水準五: 1つの経路をとにかく行き止まりまで進み、行き止まりに達したら1つ手前へ戻ってまだ調べていない別の道を進む探索方法。Depth-First Searchの略)
DFSは迷路を壁伝いに一方向へ突き進むイメージに近い。行けるところまで行って、行き詰まったら引き返す。BFSとは違って最短経路の保証はないが、実装がシンプルで再帰と相性が良く、迷路の全経路探索や、後述するトポロジカルソートの土台として使われる。
DFSは再帰呼び出し、あるいはスタック(第1巻で扱った基本データ構造)を使って実装できる。「今の頂点から行ける未訪問の頂点へ進む、行き詰まったら1つ前の頂点へ戻る」という手順は、スタックの「最後に入れたものを最初に取り出す」という性質そのものと相性が良い。BFSが「広く浅く」調べるのに対し、DFSは「狭く深く」調べる、という対比で捉えると両者の違いが記憶に残りやすい。グラフの中に閉路(サイクル)がないかを調べる用途や、迷路のすべての行き止まりを列挙する用途でもDFSは活躍する。
### 6.3 ダイクストラ法(水準五: 辺に重み[コスト]があるグラフにおいて、出発点から各頂点までの最短距離を求めるアルゴリズム。1959年にエドガー・ダイクストラが発表)
道路網で「単に道の数が少ない経路」ではなく「移動時間が最も短い経路」を求めたい場合、辺の重みを考慮する必要がある。ダイクストラ法は「まだ確定していない頂点の中から、出発点からの暫定距離が最も小さいものを選び、その頂点を経由して隣接頂点の距離を更新していく」という手順を、貪欲法の考え方を応用して繰り返す。カーナビの経路探索や路線検索サービスの基盤技術の一つである。ただし辺の重みが負の値を含む場合には正しく動作しないという制約があり、その場合は別のアルゴリズムが必要になる。
この手順を具体的にイメージするために、出発点をS、各頂点への暫定距離を無限大(未確定)から始めるとする。Sからの距離は0で確定させ、Sに隣接する頂点の暫定距離を辺の重みで更新する。次に「まだ確定していない頂点の中で暫定距離が最小のもの」を確定させ、その頂点を経由してさらに先の頂点の暫定距離を更新する。この「最小の暫定距離を持つ頂点から確定させていく」という選び方自体が貪欲法の応用であり、辺の重みが非負である限り、一度確定させた距離がその後の更新で悪化することはないという性質が、ダイクストラ法の正しさを支えている。全頂点の距離が確定するまでこの手順を繰り返すだけで、出発点から到達可能なすべての頂点への最短距離が求まる。
### 6.4 トポロジカルソート(位相ソート、水準五: 「AがBより先」という依存関係を持つ有向グラフにおいて、すべての依存関係を満たす順序に頂点を並べ替える手法)
大学の履修計画を思い浮かべてほしい。「基礎科目を履修してからでないと発展科目を履修できない」という依存関係がある場合、トポロジカルソートを使えば、すべての依存関係を守った履修順序を機械的に導出できる。ソフトウェアのビルド順序決定やタスクスケジューリングでも同じ考え方が使われる。ただし、依存関係が循環している(AがBに依存し、BがAに依存する)場合は、そもそも正しい順序が存在しないため、トポロジカルソートは失敗する。この失敗自体が「循環依存がある」という有用な検出結果になる。
---
## 第七章 計算量クラス(水準六) — 「解ける速さ」を分類する地図
ここからは視点を変える。個々のアルゴリズムを設計する話から一歩引いて、「問題そのものが、原理的にどれくらいの速さで解けるものなのか」を分類する計算量理論の世界に入る。
### 7.1 多項式時間P(水準六: 入力サイズnに対して、処理時間がn²やn³のような多項式で抑えられる問題のクラス。Polynomialの頭文字)
これまで見てきたマージソート(O(n log n))、ダイクストラ法、DPによるナップサック問題(品物数と重さ上限の積に比例)などは、いずれも入力サイズが増えても処理時間が「手に負える範囲」で増加する。このような問題の集合を計算量クラスP(水準六: 決定性の手続きで多項式時間内に解ける問題全体の集合)と呼ぶ。おおまかに言えば「実用的な時間で解ける問題」の代表格である。
計算量の増加の仕方を大まかに序列化すると、O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < ... < O(2ⁿ) < O(n!) という順に「入力が増えたときの辛さ」が増していく。O(log n)からO(n³)あたりまでの多項式時間の仲間は、入力サイズが10倍になっても処理量はせいぜい10倍から1000倍程度の増加で収まる。ところがO(2ⁿ)のような指数時間になると、入力がたった1つ増えるだけで処理量が2倍に跳ね上がる。この「多項式時間と指数時間の間にある断絶」こそが、計算量クラスPを特別な地位に置く理由であり、次に述べるNPとの対比を理解する土台になる。
### 7.2 検証可能NP(水準六: 与えられた答えの候補が正しいかどうかを多項式時間で検証できる問題のクラス。Nondeterministic Polynomial timeの略)
一方で世の中には、「答えを一から探すのは大変だが、答えの候補を見せられれば正しいかどうかはすぐに確認できる」問題がある。この性質を持つ問題の集合を計算量クラスNPと呼ぶ。
たとえば巡回セールスマン問題(TSP、水準六: すべての都市をちょうど1回ずつ訪れて出発点に戻る、総移動距離が最小の巡回経路を求める問題)を考える。「総距離X以下の巡回経路が存在するか」という問いに対して、誰かが「この順番で回ればX以下です」という経路を提示してくれれば、実際に距離を合計してX以下か確かめるのは一瞬でできる(検証は多項式時間)。しかし、その経路を自力で一から探し出すのは、都市の数が増えると爆発的に難しくなる。
**検算例3: 組み合わせ爆発の桁感覚**。巡回セールスマン問題で考えられる訪問順序の総数は、都市数をnとすると(n-1)!/2通りある。n=20の場合、(20-1)!/2はおよそ6×10¹⁶通り(6京通り)にのぼる。n=50まで増やすと(49)!/2はおよそ3×10⁶²通りという、宇宙に存在する原子の総数(およそ10⁸⁰個と見積もられることが多い)に迫るほどの桁数になる。この誇張のない桁感覚こそが、「なぜ総当たりでは解けないのか」を実感させてくれる。ここで重要なのは、これは「アルゴリズムの工夫が足りない」という次元の話ではなく、問題の性質そのものに根差した壁だという点である。
このP と NP の関係を図で整理する。
```
計算量クラスの包含関係(現在の理解、P≠NPは未解決)
┌─────────────────────────────────────┐
│ NP │
│ (検証が多項式時間でできる問題全体) │
│ │
│ ┌───────────────────────────────┐ │
│ │ P │ │
│ │ (多項式時間で解ける問題) │ │
│ │ 例: マージソート・ダイクストラ法 │ │
│ │ DPによるナップサック問題 │ │
│ └───────────────────────────────┘ │
│ │
│ ┌─────────────────────┐ │
│ │ NP完全 │ │
│ │ NPの中で最も難しい層 │ │
│ │ 例: TSP・SAT │ │
│ └─────────────────────┘ │
└─────────────────────────────────────┘
P⊆NPは証明済み。P=NPかP⊊NPかは未解決(P≠NP予想)。
NP完全の一つでも多項式時間で解ければ、NP完全すべてがPに含まれることが証明されている。
```
P⊆NP(PはNPに含まれる)であることは証明されている。多項式時間で解ける問題は、その解自体も当然多項式時間で検証できるからだ。問題は「NPに属する問題は、実はすべてPにも属するのか(P=NP)、それともPより真に広いのか(P⊊NP)」という点であり、これがコンピュータ科学における最大級の未解決問題であるP≠NP予想(水準六: 「多項式時間で解ける問題の集合」と「多項式時間で検証できる問題の集合」が一致するかどうかを問う未解決問題。2000年にクレイ数学研究所がミレニアム懸賞問題の一つに指定)である。
### 7.3 NP完全(水準六: NPに属する問題の中で、他のすべてのNP問題を多項式時間で変換[還元]して表現できる、NPの中で最も難しいとされる問題群)
すべてのNP問題が同じ難しさというわけではない。1971年頃、スティーブン・クックとレオニード・レビンが独立に切り開いた理論(クック・レビンの定理)により、NPの中には「これが多項式時間で解ければ、NPに属するすべての問題が多項式時間で解ける」という特別な問題群が存在することが示された。これがNP完全である。
その最初の具体例として示されたのが充足可能性問題SAT(サット、水準六: 複数の論理変数からなる論理式[AND・OR・NOTの組み合わせ]に対して、式全体をTRUEにする変数の割り当てが存在するかを判定する問題。Satisfiabilityの略)であった。SATがNP完全であることが示されたことで、そこから他の多くの問題(巡回セールスマン問題を含む)へと還元(変換)する形で、次々とNP完全性が証明されていった。
還元(かんげん、水準六: ある問題を、別の問題を解く手続きを使って多項式時間で解けるように変換すること)という考え方は、NP完全性の証明の心臓部にあたる。「問題Aを解きたければ、Aのインスタンスを問題Bのインスタンスへ多項式時間で変換し、Bを解いて、その答えをAの答えへ逆変換すればよい」という筋道が成り立つとき、「AはBへ還元できる」という。クックとレビンが示したのは、NPに属するすべての問題がSATへ還元できるという事実であり、これによって「SATさえ多項式時間で解ければ、NPのすべての問題が多項式時間で解けてしまう」という強力な連鎖が成立する。SAT以降、巡回セールスマン問題やナップサック問題の判定版(ある価値以上を達成できる詰め方が存在するかを問う形)、グラフの彩色問題など、数百種類にのぼる問題がこの還元の連鎖でNP完全であると証明されてきた。これらの問題は見た目こそ大きく異なるが、還元という橋で繋がれた「同じ根を持つ困難さ」を共有している。
「速く解ける」ことと「答えを速く確かめられる」ことの違いこそが、この章全体を貫く最重要の論点である。NP完全問題は、答えの検証は簡単なのに、答えの発見は(少なくとも現在知られている方法では)指数時間かかってしまう。そして、この壁が「アルゴリズムがまだ発見されていないだけ」なのか「原理的に存在しえない壁」なのかは、2026年現在も証明されていない。これがP≠NP予想が未解決であるという事実であり、本冊では誇張せずそのまま明記する。
---
## 第八章 現実的対処と計算の限界(水準六) — 完璧を諦めて、賢く近づく
NP完全問題に現実で出会ったとき、私たちは指数時間の壁を前に立ち尽くすしかないのだろうか。実務の世界では、いくつかの現実的な対処法が発展してきた。
### 8.1 近似アルゴリズム(水準六: 最適解そのものではなく、最適解に近いことが数学的に保証された解を、現実的な時間で求めるアルゴリズム)
巡回セールスマン問題の一部の変種では、「最適解の一定倍以内(たとえば2倍以内)であることが保証された解」を多項式時間で求める近似アルゴリズムが存在する。完璧な最適解は諦めるが、「どれだけ悪くてもこの程度までしか外れない」という保証付きで妥協するという発想だ。
近似アルゴリズムが成立する背景には、「最適解ぴったりを求める判定問題はNP完全でも、ある程度の誤差を許した近似解であれば多項式時間で求められる」という問題ごとの性質の違いがある。逆に、どれだけ緩い近似でもNP完全性が崩れない(近似すら困難な)問題も存在し、この「近似のしやすさ」自体を分類する近似困難性の理論も発展している。実務では、荷物の配送計画やネットワークの回線設計など、厳密な最適解を待っていては業務が回らない場面で、この近似アルゴリズムが日常的に活躍している。
### 8.2 ヒューリスティクス(発見的手法、水準六: 理論的な最適性の保証はないが、経験的に良い解を高速に導くことが多い実用的な手法)
保証はなくても経験的にうまくいく手順も広く使われている。局所探索(現在の解を少しずつ改良していく)や、貪欲法をベースにした近似的な手順などがこれにあたる。理論的な裏付けよりも、実務での実績が採用の理由になる領域である。
### 8.3 乱択アルゴリズム(らんたくアルゴリズム、水準六: 計算の途中でランダムな選択を取り入れることで、平均的に高速な処理や、偏りのない結果を得るアルゴリズム)
あえてランダム性を導入することで、最悪の場合の入力に引っかかりにくくしたり、平均的な実行時間を改善したりする設計もある。整列アルゴリズムのピボット選択にランダム性を加える手法などが代表例である。
なぜランダム性が役立つのか。多くのアルゴリズムには「特定の入力パターンに対しては極端に遅くなる」という弱点がある。もし攻撃者や偶然によって、その苦手な入力パターンばかりが与えられ続けたら、システム全体の性能が悪化してしまう。ここでランダムな選択を紛れ込ませておけば、「どの入力に対しても、平均すればまず遅くならない」という統計的な安心感が得られる。乱択アルゴリズムは、最悪の場合を確実に避けるわけではないが、「意図的に苦手な入力を突かれるリスク」を大幅に下げるという実務上の価値を持つ。
### 8.4 計算そのものの限界 — 停止性問題(ていしせいもんだい、水準六: あるプログラムが与えられた入力に対して、いつか停止するか、それとも永遠に動き続けるかを、あらゆるプログラムに対して判定できる万能な方法は存在しないことを示した理論的な結果。1936年にアラン・チューリングが証明)
最後に、NP完全よりもさらに根源的な限界に触れておく。P対NPは「多項式時間で解けるかどうか」という速さの分類だったが、停止性問題はそもそも「有限の手順でいつか答えが出るかどうか」を問う、計算可能性そのものに関わる話だ。
チューリングは1936年、「任意のプログラムと入力を受け取り、それが停止するか無限ループするかを常に正しく判定できる、万能な判定プログラムは存在しない」ことを数学的に証明した。この証明の直感は「もしそのような万能判定プログラムが存在すると仮定すると、自己言及的な矛盾(判定プログラム自身を入力にして、判定結果と逆の動作をするプログラムを作れてしまう)が生じる」というものだ。これはNP完全問題のように「時間さえかければ解ける」種類の壁ではなく、「原理的にアルゴリズムそのものが存在しない」という、計算量理論よりさらに一段深い計算可能性理論の壁である。P対NPの未解決性とはレベルの異なる話だが、「アルゴリズムには限界がある」という同じ精神を共有する話として、この章の締めくくりに置く。
---
## 終章 — この地図が繋がる先
本冊で見た「解けなさ」の理論は、決して悲観的な結論ではない。むしろ、NP完全問題の困難さは、現代社会を支えるある技術の土台になっている。
暗号(→BOOK-0073)の安全性の多くは、「ある計算は一方向には簡単だが、逆方向には途方もなく難しい」という非対称性に依拠している。素因数分解の困難さや、離散対数問題の困難さは、まさに本冊で扱った「検証は簡単・発見は困難」という構造そのものであり、NP完全問題そのものではないにせよ、同じ精神を持つ計算困難性が暗号の安全性を根本から支えている。P≠NPが成り立たず、もしいつかNP完全問題が多項式時間で解けてしまえば、現代暗号の多くの前提が揺らぐことになる。
また機械学習(→BOOK-0087)の学習過程の多くも、本質的には巨大な組み合わせ最適化問題であり、DPや貪欲法、近似アルゴリズムの考え方が土台として流れ込んでいる。ネットワーク(→BOOK-0070)における経路制御にも、ダイクストラ法や最小全域木の考え方が生きている。そして、これらすべての基礎には、第1巻(→BOOK-0066)で学んだデータ構造と基礎アルゴリズム、さらにその根源にあるコンピュータそのものの仕組み(→BOOK-0010)、そして数論(→BOOK-0074)の素数の性質が横たわっている。
「速く解ける」と「解けなさを見抜く」は、一見正反対に見えて、実は同じ地図の両面である。次にこの地図を広げるとき、あなたは暗号の扉、あるいは機械学習の扉、どちらから入ってもよい。どちらの奥にも、本冊で描いた計算量の風景が待っている。
**フロンティア(未解決の最前線)**: P≠NP予想は、2026年現在も証明されていない。多くの研究者は「P≠NPだろう」と予想しているが、これはあくまで予想であり証明ではない。もしP=NPが証明された場合(あるいはP=NPを示す具体的な多項式時間アルゴリズムが発見された場合)、暗号技術を含む現代の情報基盤の多くが根本的な見直しを迫られる。逆にP≠NPが証明されたとしても、それは「NP完全問題を厳密に多項式時間で解く方法がない」ことを確定させるだけで、近似アルゴリズムやヒューリスティクスによる実務上の対処の価値を損なうものではない。この巨大な未解決問題こそが、次の世代の探求者を待っている。
# BOOK-0116 アルゴリズム 第2巻 — 賢い探索と「解けなさ」の地図(情報派生 第2巻)