計算量クラス P・NP と NP完全性

「解く」と「検証する」を分ける

計算量クラスの議論は、問題を判定問題（答えが Yes/No）に落として考えます。鍵は「解を見つけるコスト」と「与えられた解が正しいか確かめるコスト」を区別することです。

• P（Polynomial time）: 入力サイズ n に対し、O(n^k) で解ける判定問題の集合。例: 最短経路、ソート済みかの判定、素数判定（AKS）。
• NP（Nondeterministic Polynomial time）: 「Yes」である証拠（証明書）を渡されたら、それが正しいか多項式時間で検証できる問題の集合。

NP の名は「非決定性チューリング機械が多項式時間で解ける」に由来し、「Non-Polynomial（非多項式）」の略ではありません。ここを誤解すると以降が崩れます。

包含関係を文章で整理する

4つのクラスの関係は、外側に向かって難しくなる入れ子構造として捉えます。

• P … 解ける。NP の内側にある最も御しやすい領域。
• NP … 検証できる。P を内包する。
• NP完全（NP-complete） … NP に属し、かつ NP のすべての問題をそこへ多項式時間で還元できる「NP の中で最も難しい」問題群。
• NP困難（NP-hard） … 「NP のすべての問題を還元できる」だけを要求し、自分が NP に属する必要はない。NP完全 ⊆ NP困難。

文章で書くと包含は次の通りです。P ⊆ NP、NP完全 = NP ∩ NP困難、NP完全 ⊆ NP困難。NP困難は NP の外側（検証すら多項式時間でできない問題）まで張り出します。

還元 ―「Aが解ければBも解ける」を作る

クラス間の難しさをつなぐ道具が多項式時間還元（polynomial-time reduction）です。問題 A を問題 B に還元するとは、A の任意の入力 x を多項式時間で B の入力へ変換する関数 f を作り、x が A で Yes ⇔ f(x) が B で Yes を成り立たせること。

この向きが直感と逆になりがちなので注意します。「A を B に還元できた」なら、B を解く手段があれば A も解ける＝ B は A 以上に難しい、と読みます。

入力 x ──(多項式時間の変換 f)──▶ 入力 f(x)
  │                                  │
  ▼                                  ▼
Aで Yes/No  ⇔（同値を保証）⇔   Bで Yes/No

NP完全性の証明は、この還元を使った連鎖で行います。

• ある問題 X を NP に属することを示す（証明書と多項式検証を提示）。
• 既知の NP完全問題 Y を Y ≤p X のように X へ還元する。

これで「NP の全問題は Y に押し込めて、Y は X に押し込める」ので、X も NP完全になります。出発点となる「最初の NP完全問題」を還元なしで確立したのが Cook–Levin の定理です。

代表問題を位置づける

同じ TSP でも、判定版（「K 以下の巡回路はあるか？」Yes/No）は NP完全、最適化版（「最短経路を出せ」）は NP困難に分類されるのが要点です。最適化版は答えが Yes/No でないため NP の定義の枠に直接は乗らず、NP困難として扱います。また 2-SAT が P で 3-SAT が NP完全という事実は、「節あたりのリテラルが2か3か」というわずかな違いが難易度の崖を生む好例です。

P=NP 問題と実務での意味

P=NP か否か（検証できる問題はすべて解けるのか）は、クレイ数学研究所のミレニアム懸賞問題の一つで未解決です。多くの研究者は P≠NP、すなわち NP完全問題には多項式時間アルゴリズムが存在しないと予想していますが、証明はされていません。

実務上は、ある問題を NP完全だと示せたら「総当たりに頼らず厳密最適解を現実的時間で得る一般手法は当面ない」と判断し、戦略を切り替える合図になります。

• 近似アルゴリズム: 最適解に対する保証付きの近似（例: 距離が三角不等式を満たす TSP の 1.5 近似）。
• ヒューリスティック / メタヒューリスティック: 局所探索、焼きなまし、遺伝的アルゴリズム。
• 問題の制限: 入力構造を限定して P に落とす（一般グラフでは NP完全でも、木や平面グラフなら多項式で解ける場合がある）。
• 指数だが賢い探索: 分枝限定法やバックトラッキングで実用的な入力を捌く。

なお、これらの判定はあくまで最悪計算時間に対する分類です。入力サイズが小さい・構造が良い場面では指数時間アルゴリズムでも十分実用になります。計算量の基礎は Big-O 記法 を、全探索を支える手法は 再帰 と データ構造 を、状態爆発と多項式・指数の境目の実例は 正規表現エンジンの内部（NFA→DFA の状態数）を合わせて押さえると、難しさの正体が立体的に見えてきます。