計算の限界とNP完全 — 総当たりが爆発するとき

巧妙なアルゴリズムを積み上げてきましたが、世の中にはどう工夫しても速く解けそうにない問題があります。都市を1つ増やすだけで経路の数が桁違いに膨らむ巡回セールスマン、答えを見つけるのは絶望的なのに答え合わせは一瞬という不思議。P対NPという計算機科学最大の難問と、それでも実務を回す近似の知恵まで、爆発を目で見ながらたどります。

1. 総当たりの爆発 — 巡回セールスマン問題

巡回セールスマン問題（TSP）：すべての都市をちょうど1回ずつ回って戻る、最短の巡回路を見つけよ。単純そのものですが、都市が n 個なら回り方は出発点を固定して (n−1)! / 2 通り。総当たりで最短を探すと、この数だけ経路長を計算することになります。

下のデモでスライダーを動かして都市を増やしてみてください。全経路を1本ずつ試す様子と、右上のカウンタが跳ね上がる速さを見れば、「総当たり」がいかに脆いかが体感できます。

巡回セールスマンの総当たり — 全経路を試して最短を探す
灰色＝いま試している経路、緑＝ここまでで見つかった最短経路。右上のカウンタは「試した経路数 / 全 (n−1)!/2 通り」。n=4 なら 3 通りで一瞬ですが、n=8 では 2,520 通り。あと数個増えるだけで人間にもコンピュータにも手に負えなくなります。
巡回路の総数 = (n − 1)! / 2 n=10 で 181,440、n=20 で約 6×1016、n=60 では宇宙の原子数を超える

2. 多項式と指数・階乗 — 成長の桁が違う

アルゴリズムの速さは「入力 n が増えたとき計算量がどう伸びるか」で分類します。O(n) や O(n²) のような多項式時間は、n が増えても伸び方が穏やか。対して O(2n) の指数時間や O(n!) の階乗時間は、ある一点から爆発します。

下のグラフは縦軸が対数（1目盛りで1000倍）であることに注意。それでも階乗と指数の曲線は画面を突き抜けます。スライダーで n を選ぶと、各アルゴリズムの計算回数と「毎秒10億回の計算機での所要時間」が出ます。多項式と指数の間には、埋めようのない壁があります。

成長の比較 — 多項式 vs 指数 vs 階乗（縦軸は対数）
青 n・水色 n²・緑 n³ が多項式、オレンジ 2n が指数、赤 n! が階乗。縦線が選択中の n で、右のパネルに計算回数と所要時間（毎秒10億回想定）が出ます。n=20 でも n³ は8000回＝一瞬なのに、n! は約240京回＝数十年。同じ問題サイズでこの差です。
POINT — 「効率的」の境界線は多項式時間 計算機科学では、多項式時間 O(nk) で解ける問題を「効率的に解ける」とみなす（このクラスを P と呼ぶ）。指数・階乗時間は入力が少し伸びただけで実行不能になるため、たとえ有限時間で終わっても「解けない」に等しい。ソート O(n log n) や最短経路 O(E log V) は P の住人、総当たりTSP は違う。

3. P対NP — 見つけるのは大変、確かめるのは一瞬

ここで計算機科学最大の謎が現れます。部分和問題：与えられた数の中から、選んで足すとちょうど目標値になる組を見つけよ。見つけるには最悪 2n 通りの部分集合を総当たりするしかない。ところが、誰かに「この組だよ」と答えを渡されたら、足し算 n 回で正しさを確かめるのは一瞬です。

下のデモで「探す（総当たり）」と「確かめる」を切り替えてください。探すときのカウンタと、確かめるときの手数を比べると、この問題の非対称性がはっきり見えます。

部分和問題 — 探すのは指数、確かめるのは線形
棒＝数、点線＝目標値。「探す」では部分集合を 0,1,2,… と総当たりし、合計が目標に届いた瞬間に停止（試行回数を表示）。「確かめる」では正解の組だけを1つずつ足して n 回で検証完了。探す手間は最悪 2n、確かめる手間は n。この落差こそ P対NP の核心です。
POINT — NP＝「答え合わせが多項式時間」のクラス NP とは「解が与えられれば、それが正しいか多項式時間で検証できる問題」の集まり。部分和・TSP・数独・パズルの多くがここに入る。P ⊆ NP は明らか（速く解けるなら速く確かめられる）。だが逆、P = NP か？——「確かめられる問題はすべて速く解けるのか？」は60年以上未解決で、100万ドルの懸賞がかかっている。

4. あきらめずに近づく — 近似とヒューリスティック

厳密な最適解が指数時間なら、実務ではどうするか。答えは「最適はあきらめ、十分よい解を高速に得る」。TSPなら最近傍法：今いる都市から一番近い未訪問の都市へ進むのをくり返すだけ。O(n²) で一瞬に巡回路が1本引けます。

下で最近傍法が瞬時に引く経路と、総当たりで求めた真の最短を比べてください。最適ではないけれど、そう悪くもない——この「そこそこ」を保証つきで速く出すのが近似アルゴリズムの世界です。

最近傍法 vs 最適 — 一瞬の近似は最短にどこまで迫れるか
オレンジ＝最近傍法が貪欲に伸ばす経路（O(n²) で瞬時）。「最適経路を表示」を押すと、総当たりで求めた真の最短が緑で重なります。最近傍法は最適の数％〜数十％増しに収まることが多く、都市が何千あっても即答できる——厳密解が絶望的な問題への現実的な回答です。
注意 — 近似にも限界と保証がある ヒューリスティックは速いが「どれだけ最適に近いか」の保証がないものも多い。一方できちんと設計された近似アルゴリズムは「最適の2倍以内」などの保証を持つ（距離が三角不等式を満たすTSPなら Christofides 法が 1.5倍保証）。だが問題によっては、近似することすらNP困難と証明されているものもある。「とりあえず貪欲」で済むかは問題の性質次第だ。

5. まとめ — 限界を知って、賢くあきらめる

一歩先へ — NP完全と、もし P=NP なら NPの中でも最も難しい問題たちをNP完全と呼ぶ。すごいのは、TSP・部分和・SAT（論理式充足）・グラフ彩色などが互いに多項式時間で変換し合えること（クック–レビンの定理に始まる帰着の網）。だからどれか1つでも多項式時間で解ければ、全部が解ける＝P=NP。もしそうなら暗号は崩壊し、あらゆる最適化が一瞬になる——世界が一変する。だが現実には、SATソルバのように「理論上は最悪指数だが実用上は驚くほど速い」道具が発達し、私たちは限界と折り合いをつけて生きている。