計算複雑性とNP困難の地図

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：代表的な組合せ問題　|　関連：局所探索と近傍

要点（BLUF）

P＝多項式時間で解ける問題、NP＝解の正しさを多項式時間で検証できる問題。
NP 困難＝NP のどの問題も多項式時間で帰着できる「少なくとも同じくらい難しい」問題。TSP・一般ナップサック・集合被覆が該当。
難しい問題には 近似アルゴリズム・緩和・メタヒューリスティクスで折り合う。「厳密に速く」は一般に望めない。

概念 ── 何が「難しい」のか

最適化の難しさは「規模 $n$ に対して計算時間がどう伸びるか」で測る。多項式（ $n^2,\ n^3$ ）なら実用的、指数（ $2^n,\ n!$ ）なら手に負えない。組合せ最適化（代表的な組合せ問題）が難しいのは、選択肢が 指数的に増えるから。

graph TD
  P["P: 多項式時間で解ける (最短路・割当・LP)"] --> NP["NP: 解を多項式時間で検証できる"]
  NP --> NPC["NP完全: NPの中で最も難しい (NP かつ NP困難)"]
  NPH["NP困難: NPの全問題が帰着する難しさ"] --> NPC
  NP --> NPH2["TSP・ナップサック・集合被覆"]

P・NP・NP困難・NP完全

P：多項式時間アルゴリズムが存在（線形計画、最短路、割当、最大流）。
NP：与えられた解の正しさを多項式時間で検証できる（解を見つけるのは別）。
NP 完全：NP に属し、かつ NP の任意の問題が多項式時間で帰着する。NP の中で最難。
NP 困難：NP の任意の問題が帰着するが、自身は NP に属さなくてもよい（最適化版はこちらが多い）。

未解決問題 P ≟ NP：「検証できる問題は解けるか？」多くの研究者は $P \ne NP$ と予想。もし正しければ、TSP のような NP 困難問題に 多項式時間の厳密アルゴリズムは存在しないことになる。

組合せ爆発を数値で見る

巡回セールスマン（TSP）の巡回路は $(n-1)!/2$ 通り、0/1 変数の部分集合は $2^n$ 通り。 $n$ が増えると桁が暴走する。

import math

print(f"{'n':>3} | {'TSP巡回路数 (n-1)!/2':>22} | {'部分集合数 2^n':>16}")
for n in [5, 10, 15, 20, 25]:
    tsp = math.factorial(n-1) // 2     # TSPの異なる巡回路の数
    subsets = 2**n                     # 0/1がn個の組合せ数
    print(f"{n:>3} | {tsp:>22,d} | {subsets:>16,d}")

# n=25 のTSPを全探索したら? 10億(1e9)通り/秒 で評価できるとして
tours = math.factorial(24) // 2
years = tours / 1e9 / (60*60*24*365)
print(f"\nn=25 のTSP全探索: 巡回路 {tours:.3e} 通り, 所要 {years:.3e} 年")

実行結果：

  n |   TSP巡回路数 (n-1)!/2 |   部分集合数 2^n
  5 |                     12 |               32
 10 |                181,440 |            1,024
 15 |         43,589,145,600 |           32,768
 20 | 60,822,550,204,416,000 |        1,048,576
 25 | 310,224,200,866,619,719,680,000 |       33,554,432

n=25 のTSP全探索: 巡回路 3.102e+23 通り, 所要 9.837e+06 年

たった25都市の TSP でも、1秒に10億通り評価できる計算機で 約980万年かかる。これが「指数時間は実用にならない」の意味。全探索は無理なので、賢い枝刈り（分枝限定法）か、最適性を諦めた近似（メタヒューリスティクス章目次）が要る。

難しさとどう折り合うか

NP 困難でも実務は止まらない。折り合いの付け方：

近似アルゴリズム：最適から一定比率以内を保証（集合被覆の貪欲は $\ln n$ 近似、距離が三角不等式を満たす TSP は 1.5 近似の Christofides 法）。
緩和：LP 緩和・ラグランジュ緩和・凸緩和（凸最適化問題と双対理論）で上下界を挟む。
分枝限定／分枝カット：厳密だが指数最悪。実問題では十分速いことも多い（分枝限定法・切除平面法）。
メタヒューリスティクス：保証はないが、大規模で良い解を速く（メタヒューリスティクス章目次）。
擬多項式・パラメータ化：ナップサックは容量に比例する DP で解ける（弱 NP 困難）。

数式の直観的意味

NP 困難の本質は「検証は易しいが探索は難しい」の非対称性。解を1つ渡されれば正しさは多項式時間で確認できるのに、その解を 見つけるには指数的に広い空間を探さねばならない（ $P\ne NP$ なら）。最適化が難しいのは、単に解を1つ見つけるのでなく「最良であることの証明」まで要るから ── これは「より良い解が存在しない」ことの確認で、緩和の上界（整数計画とは・LP緩和）が一致して初めて達成される。だから最適化の高速化は「探索を間引く（分枝）」と「上界を締める（カット・緩和）」の両輪になる。

⚠️ よくある誤解・落とし穴

「NP 困難＝絶対に解けない」ではない。最悪が指数というだけで、構造の良い実問題は速く解けることも多い。
「NP 完全」と「NP 困難」を混同しない：NP 完全は NP の中の最難、NP 困難はそれ以上（最適化版の多く）。
近似比の保証と実性能は別：保証が緩くても実データで良いことも、逆もある。
多項式時間でも指数 $n^{10}$ なら遅い。理論の「効率的」と実務の「速い」は必ずしも一致しない。