P対NP問題とNP完全性(NP-Completeness)
1. 概要
A. 定義
NP完全性(NP-Completeness)とは、非決定性多項式時間(NP)に属する決定問題のうち、NPに属するすべての問題が多項式時間還元(polynomial-time reduction)で帰着できる「最も難しい」問題の集合を指し、そのいずれか一つにでも多項式時間アルゴリズムが発見されればNP全体がPと等しくなるという点で、P対NP問題(P versus NP problem)の核心に位置する概念である。
P対NP問題は計算複雑性理論の最も根本的な未解決難問であり、アルゴリズムで解けるものと効率的に解けるものの境界を問う問いである。P対NP問題は「解を検証するのが容易な(多項式時間)問題は、解を探すのも容易か」という単一の問いに要約される。数独を例にとると、完成した答えが規則に合うか確認する作業はマス数に比例してすぐ終わるが、空の格子から答えを最初から見つけ出す作業は格子が大きくなるほど劇的に難しくなる。このように「検証は容易だが探索は難しそうに見える」数多くの問題が、果たして本質的に難しいのか、それともまだ速い方法を見つけていないだけなのかを問うのがP対NP問題であり、NP完全性は「これらの問題が運命を共にする」という事実を数学的に束ねる装置である。
ここで「容易」と「難しい」を厳密に定義するために、複雑性理論は多項式時間を効率性の基準線とする。ある問題が入力サイズの多項式に比例する時間内に解ければ「扱いやすい(tractable)」問題に、指数時間を要するように見えれば「扱いにくい(intractable)」問題に分類し、P対NP問題はまさにこの二つの世界の間に巨大な問題集合がどちらに属するかを分ける境界線論争である。NP完全性は、その境界線上に危うく置かれた、どちらに属するのかまだ誰も証明できていない問題を一つに束ねて名づけたものである。
NP完全性が情報技術の実務に与える含意は明確である。ある問題がNP完全と判明すれば、その問題に対して「すべての入力で速く正確な」アルゴリズムを探す試みは、数十年にわたる世界的難問の壁に突き当たるのと同じであるから、設計者は直ちに戦略を近似アルゴリズム・ヒューリスティック・問題制約・特殊入力へ転換しなければならない。したがって技術士にとってNP完全性は抽象的理論ではなく、「この問題に完璧な最適アルゴリズムを要求するのが合理的か、それとも十分に良い解で妥協すべきか」を分ける実務的判断基準である。
B. 登場背景と必要性
1960年代までアルゴリズム研究は個別問題ごとにより速い方法を探すことに集中していたが、巡回セールスマン問題(TSP)・充足可能性問題(SAT)・整数計画法のように「直観的には容易に見えるのに数十年努力しても多項式時間解法が出ない」問題が積み重なるにつれ、これらが偶然難しいのではなく共通の構造的障壁を共有するのではないかという疑いが強まった。1971年にStephen Cookが、1973年にLeonid Levinが独立に「SAT問題はNPのすべての問題が還元される普遍的難問である」ことを証明し(クック・レビンの定理)、ようやく「最も難しい問題」という概念が数学的に定義された。翌年Richard Karpが21個の代表問題をNP完全として束ね、この概念が広範な実問題に適用されることを示した。
この発見の必要性は「不可能に近い努力の浪費を防ぐ」点にある。NP完全性理論がなければ、技術者はある最適化問題を前に「もう少し頭を使えば速いアルゴリズムが出るはず」という空しい期待で資源を使い果たしかねない。しかし問題がNP完全であることを還元で一度だけ証明しておけば、「この問題の効率的な完全解法を探すことはP=NPを証明するのと同じくらい難しい」という強力な下界を得て、努力の方向を現実的な代替へ直ちに転じられる。すなわちNP完全性は「解けないことの証明」ではなく「容易に解ける可能性が希薄であることの証明」として、工学的意思決定の羅針盤の役割を果たす。
さらにNP完全性は現代情報セキュリティの土台とも接している。暗号方式の安全性は「鍵なしで暗号文を解く問題が計算的に難しい」という仮定に依存するが、もしP=NPが真と判明すれば、RSA([[rsa-dsa]])を含む多くの公開鍵暗号が原理的に無力化されうる。このようにP対NP問題は単なる理論的好奇心を超え、アルゴリズム設計・最適化・暗号・人工知能探索など情報技術全般の可能性と限界を規定する根本的問いであるから、技術士はその構造と実務的対応を正確に理解しなければならない。
2. 計算複雑性クラスの構造
P対NP問題を理解するには、まず決定問題(答えが「はい/いいえ」の問題)を難易度によって分類する複雑性クラス(complexity class)の地形を把握しなければならない。下の概念図は、Pが広く受け入れられているP≠NPの世界におけるクラス包含関係を表す。
flowchart TB
subgraph NPSPACE["NPの世界 (P≠NP仮定)"]
P["P<br/>(多項式時間で解決)"]
NPC["NP完全<br/>(NPで最も難しい問題)"]
NPonly["NP (その他)<br/>例: グラフ同型?"]
end
NPHARD["NP困難<br/>(NP-hard、NPと同等かそれ以上)"]
P --> NPonly
NPonly --> NPC
NPC --> NPHARD
NPHARD --> UNDEC["決定不能問題<br/>(停止問題など)"]
P(Polynomial time)は、入力サイズnに対してO(nᵏ)のように多項式時間内に決定的アルゴリズムで解ける問題の集合である。ソート([[sorting-algorithms]])、最短経路、最小全域木のように「実務で効率的に解ける」と呼ぶ問題がほとんどここに属する。Pを「効率的に解ける問題」の代用(proxy)とする理由は、多項式時間は入力が大きくなってもコストが緩やかに増えてハードウェアの発展で吸収可能である一方、指数時間は入力が数十増えるだけでも宇宙の年齢を超える計算を要するからである。この対比は数値で見ると鮮明である。n=50のときn³は約12万演算で瞬時だが2ⁿは約10¹⁵で数日かかり、n=100なら2ⁿは10³⁰を超え、現存するスーパーコンピュータでも事実上不可能である。この格差がPと指数時間問題を分ける実質的境界であり、「多項式対指数」という抽象的区分がなぜ工学的に決定的かを説明する。
NP(Nondeterministic Polynomial time)は、「正答候補(証明書、certificate)が与えられたとき、それが正しいかを多項式時間に検証できる」問題の集合である。核心は「探す」ことではなく「確認する」ことの難易度である点だ。例えばあるグラフにサイズkのクリーク(完全部分グラフ)が存在するかを問う問題は、候補頂点集合を受け取ればすべての対が連結かO(k²)で確認できるのでNPに属する。すべてのP問題は当然NPに属する(検証は再計算で代替可能)のでP⊆NPは自明であり、世紀の難問はその逆であるNP⊆P、すなわちP=NPが成り立つかである。
NP困難(NP-hard)は「NPのすべての問題が多項式時間に還元される」問題を意味し、必ずしもNPに属する必要はなく、決定問題でない最適化問題や、さらには決定不能問題まで含みうる。NP完全(NP-complete)はまさにこのNP困難でありながら同時にNPにも属する問題、すなわち「NPの中で最も難しい問題」として定義される。下の表は四つのクラスの関係を整理したものだが、各定義の「なぜ」は上の散文の説明で補完すべきである。
| クラス | 定義(核心) | NP所属 | 代表例 |
|---|---|---|---|
| P | 多項式時間で解決可能 | 常にNPに属す | 最短経路、ソート、2-SAT |
| NP | 多項式時間で解を検証可能 | 定義上NP | ハミルトン経路、部分和、クリーク |
| NP完全 | NP困難 ∩ NP | NPに属す | 3-SAT、TSP(決定形)、グラフ彩色 |
| NP困難 | NP全体が還元される難度 | 属す場合も否も | TSP(最適化形)、停止問題 |
一方、複雑性の地形にはco-NPという双子のクラスも存在する。NPが「はい」という答えを多項式時間に検証できる問題なら、co-NPは「いいえ」という答えを多項式時間に検証できる問題、すなわちNP問題の補集合である。例えば「この論理式は充足不能か(UNSAT)」はco-NPの代表問題である。NP=co-NPかも未解決であり、もしあるNP完全問題がco-NPにも属することが判明すれば、NP=co-NPとなって複雑性理論の多くの予想が崩れる。このように決定問題の「はい/いいえ」の非対称性自体が深い構造的意味を持つ点は、NP完全性が単なる分類を超え計算の本質を探究する理論であることを示す。
また実務の最適化問題は大抵「最小コストはいくらか」を問う最適化形だが、NP完全性は「コストがk以下の解が存在するか」という決定形で定義される。これは恣意ではなく、決定形と最適化形が多項式時間内で互いに還元可能だからである。決定形解法器を二分探索で繰り返し呼び出せば最適値を多項式時間に求められる。したがって「決定形TSPがNP完全」という命題は、すなわち「最適化形TSPも効率的に解くのが難しい」を含意し、理論と実務をつなぐ橋となる。
この構造で最も重要な洞察は、NP完全問題が一つの運命共同体である点だ。定義上、任意のNP完全問題Aは他のすべてのNP問題を包含するので、もしAに対する多項式時間アルゴリズムが発見されれば、還元の鎖に沿ってNPのすべての問題が多項式時間に解けてP=NPが成り立つ。逆にいずれか一つでも多項式時間に解けないこと(指数下界)が証明されればP≠NPが確定する。すなわち、数千に及ぶNP完全問題のうちたった一つの運命が全体の運命を決める。
3. 多項式時間還元とNP完全性の証明
NP完全性概念のエンジンは多項式時間還元(polynomial-time reduction)である。問題Aを問題Bに還元するとは、Aの任意の入力を多項式時間にBの入力へ変換しつつ、「Aの答えがはい」であることと「変換されたBの答えがはい」であることが正確に一致するようにすることを意味する(記号でA ≤ₚ B)。この関係が成り立てば「Bが容易ならAも容易」が自動的に従うので、還元は問題間の難易度を伝える通路となる。
flowchart LR
START["新問題Xの<br/>NP完全性証明"] --> S1["段階1: XがNPに属す<br/>(解検証が多項式時間)"]
S1 --> S2["段階2: 既知のNP完全問題Yを選択<br/>(例: 3-SAT)"]
S2 --> S3["段階3: Y ≤ₚ X 還元を構成<br/>(Y入力をX入力へ多項式変換)"]
S3 --> S4["段階4: 変換が答えを保存することを証明<br/>(はい↔はい、いいえ↔いいえ)"]
S4 --> DONE["XはNP完全<br/>(Yの難度が伝達)"]
S1 -. "一つでも失敗時" .-> FAIL["NP完全でない<br/>(別の接近が必要)"]
S3 -. "一つでも失敗時" .-> FAIL
新しい問題XがNP完全であることを証明する標準手順は、上のフローチャートのように二つの軸で構成される。第一に、XがNPに属することを示す(正答候補が与えられれば多項式時間に検証可能であることを提示)。第二に、既にNP完全と知られた問題YをXへ還元(Y ≤ₚ X)して「Yと同じくらい難しい」という下界を伝達する。ここで還元の方向が核心であり、YをXへ還元してこそ「Yの難しさがXに相続」され、方向を逆にすれば何も証明できない。この「還元方向の罠」は試験と実務の双方で最も多い誤りであるから、必ず注意しなければならない。
このすべての還元の鎖の出発点こそがクック・レビンの定理(Cook-Levin Theorem)である。この定理は、還元すべき既知のNP完全問題がまだ一つもなかった状態で、SAT(ブール充足可能性)問題がNP完全であることを直接証明した。証明の骨子は「任意のNP問題を解く非決定性チューリング機械の計算過程全体を、その機械が正答を受理するか否かと同値な巨大な論理式(CNF)として多項式時間に符号化できる」ことである。すなわちどんなNP問題でもその「計算の歴史」をSAT式に翻訳できるので、SATを解けばすべてのNP問題を解ける。SATが最初のNP完全問題として確定して以降は、新問題の証明が「無から有を作る」作業から「既に知る難問一つを還元する」比較的機械的な作業へと変わった。
実際の還元が難易度を伝える通路になりうる根拠は、その推移性(transitivity)にある。A ≤ₚ BかつB ≤ₚ CならばA ≤ₚ Cが成り立つ。多項式の合成は依然として多項式だからである。クック・レビンの定理でSATがNP完全と確定し、SAT ≤ₚ 3-SAT ≤ₚ クリーク ≤ₚ 頂点被覆 ≤ₚ … と還元の鎖が伸びていけば、この鎖上のすべての問題が自動的にNP完全になる。Karpが21個の問題を一度にNP完全として束ねられたのもこの推移性のおかげであり、今日知られる数千のNP完全問題はすべてこの一つの根(SAT)から伸びた巨大な還元の木の枝である。新問題を証明するとき「どの既知問題から還元するか」をうまく選べば証明が劇的に簡潔になるので、還元の出発点の選択自体が設計的判断である。
実際の還元の具体例として3-SATからクリーク問題への還元を挙げられる。節(clause)がm個の3-SAT式が与えられると、各節の三つのリテラルを頂点とする3m個の頂点を作り、互いに異なる節に属しつつ矛盾しない(一方がxで他方が¬xでない)リテラル同士だけを辺で結ぶ。こうして作ったグラフにサイズmのクリークが存在することと、元の式が充足可能であることが正確に一致することを示せば還元が完成する。頂点・辺の生成が式サイズの多項式で終わるので多項式時間還元であり、この一度の構成で「SATが難しければクリークも難しい」が証明される。このような具体的な還元設計能力がNP完全性を扱う核心技術である。
実務でよくある誤解は「自分の問題を既に知る容易な問題に変えられるから容易だ」と性急に結論づけることだ。しかしNP完全性を「証明」するには、逆に難しい既知問題を自分の問題へ還元しなければならない。自分の問題を容易な問題へ還元するのはむしろ「自分の問題が容易かもしれない」という上界を与える正反対の作業である。この方向の混同は「NP完全を証明した」という誤った自信につながり設計判断を歪めうるので、還元の方向とそれが伝えるもの(下界か上界か)を各段階で明確に区別しなければならない。
4. 代表問題とP-NP境界の比較
NP完全問題と、それに「似ているが」Pに属する問題を並べて比較すると、難易度の境界がいかに微妙な条件差で分かれるかが明らかになる。次の表とその後の散文は代表事例を整理する。
| 難しい問題(NP完全) | 似た容易な問題(P) | 境界を分ける条件 |
|---|---|---|
| 3-SAT(節あたりリテラル3個) | 2-SAT(節あたり2個) | 節長2以下なら含意グラフで線形解決 |
| ハミルトン経路(全頂点1回) | オイラー経路(全辺1回) | 辺条件は次数検査で多項式解決 |
| 一般グラフ3彩色 | 2彩色(二部グラフ判定) | 色2個ならBFSで線形判定可能 |
| 0/1ナップサック(整数選択) | 分数ナップサック(分割可) | 分割可能なら貪欲([[greedy-algorithm]])で最適 |
| TSP(最短巡回) | 最小全域木(MST) | 巡回(閉路)制約が貪欲を崩す |
最も劇的な例は2-SATと3-SATの対比である。節ごとに変数が2個以下なら、「aが真ならbも真でなければならない」式の含意を辺で表した含意グラフで強連結成分を見つけ、線形時間に充足可能性を判定できる。しかし節あたりの変数が3個に増える瞬間、この優雅な構造が消えてNP完全になる。リテラル一つの差が「線形時間」と「指数時間推定」を分けるのだ。これはNP完全性が問題の見た目ではなく内在する組合せ構造から生じることを示す。
ナップサック問題の二つの変種も教訓的である。物を分割できる分数ナップサックは単位重量あたり価値が高い順に詰める貪欲戦略が証明可能に最適だが、分割できない0/1ナップサックは「今詰めるか否か」の離散的選択が未来に及ぼす影響のため貪欲が崩れ、NP完全になる。ただし0/1ナップサックは動的計画法([[dynamic-programming]])でO(nW)に解けるが、これは見かけは多項式でもWが数の「値」なので入力ビット数に対しては指数的な擬多項式(pseudo-polynomial)アルゴリズムである。このように「弱い意味のNP完全」と「強い意味のNP完全」を区別することも実務判断に重要である。
最後にTSPとMSTの対比は、制約一つが難易度を変える典型である。すべての都市を結ぶ最小コスト木(MST)は貪欲で多項式時間に解けるが、すべての都市を正確に一度ずつ訪問して出発点に戻る最小コスト巡回を要求する瞬間、NP困難になる。「木」から「ハミルトン閉路」へ変わる小さな制約追加が、効率的解法の存在有無をひっくり返すのだ。実務で物流経路最適化が難しい根本理由がまさにここにある。
これらの境界事例が与える実務的教訓は、NP完全性が特殊な数学問題にのみ潜む稀な現象ではなく情報システムのいたる所に遍在するという事実である。生産ラインの作業スケジューリング、クラウド資源配置(ビンパッキング)、コンパイラのレジスタ割当(グラフ彩色)、回路設計の配置・配線、時間割編成、通信網の周波数割当がすべてNP完全問題の変形である。一日に数えきれず出会うこれらの問題を人とシステムが「なんとか」処理するのは、現実の入力が最悪の組合せ構造を持たないか、許容可能な近似で妥協するからである。したがって技術士は「完璧を諦めた代償に何を得て失うか」を定量的に測る目を備えなければならない。
5. 深化: 実務的対応戦略とP=NPの現在
NP完全と判明した問題だからといって諦めるべきではない。実務では「すべての入力で、常に最適を、速く」という三条件のうち一つを緩和して現実的解法を得る。第一に、近似アルゴリズム(approximation algorithm)は最適解の代わりに保証された比率の解を多項式時間に提供する。例えば頂点被覆は単純な貪欲で2倍以内、ユークリッドTSPはクリストフィデスのアルゴリズムで1.5倍以内の解が保証される。第二に、ヒューリスティック・メタヒューリスティック([[metaheuristics]])は保証はないが実戦で非常に良い解を出す。現代のSATソルバ(CDCL)は理論的最悪は指数的でも数百万変数の産業用インスタンスを数秒で解き、EDA検証・ソフトウェアモデル検査などに日常的に使われる。遺伝的アルゴリズム・焼きなまし法(simulated annealing)・タブー探索のようなメタヒューリスティックは大規模TSP・スケジューリングで最適に近接した解を安定的に出し、この「理論的難解性と実務的可用性の隔たり」こそがNP完全問題を扱う現代工学の核心舞台である。
第三に、パラメータ化複雑性(parameterized complexity)は入力サイズではなく特定のパラメータk(例: 被覆のサイズ、木幅)に指数を閉じ込め、f(k)·nᶜ形のFPTアルゴリズムを設計する。kが小さく保たれる現実の入力では事実上多項式時間のように動作する。第四に、問題を特殊入力・構造に制限する戦略である。一般グラフでNP完全な多くの問題が、木・平面グラフ・区間グラフでは多項式時間に解ける。下の概念図はNP完全問題に直面したときの対応意思決定を要約する。
flowchart TB
NPC["問題がNP完全と判明"] --> Q1{"入力規模は小さいか?"}
Q1 -->|"はい"| EXACT["正確アルゴリズム<br/>(分枝限定・DP・SAT/ILPソルバ)"]
Q1 -->|"いいえ"| Q2{"保証された品質が必要か?"}
Q2 -->|"はい"| APPROX["近似アルゴリズム<br/>(保証された近似比)"]
Q2 -->|"いいえ"| HEUR["ヒューリスティック・メタヒューリスティック<br/>(遺伝・焼きなまし・局所探索)"]
NPC --> Q3{"特殊構造・小さいパラメータ?"}
Q3 -->|"はい"| FPT["FPT・制限入力アルゴリズム<br/>(木・平面・区間グラフ)"]
正確解が必ず必要なときも「指数的だができる限り速い」精密アルゴリズムが活発に研究される。例えばTSPは単純全探索がO(n!)だがHeld-Karpの動的計画法はO(2ⁿ·n²)に減らし、nが20前後なら現実的に解ける。これに関連して指数時間仮説(ETH, Exponential Time Hypothesis)は「3-SATを2^o(n)に解けない」と仮定するが、これはP≠NPより強い前提として「NP完全問題にはどれほど賢くても指数の底を1に近く減らせない」というより微細な下界を提供する。ETHを受け入れれば、数多くの問題に対し「このアルゴリズムより本質的に速いものは不可能」という条件付き最適性を論証でき、アルゴリズム研究の舵の役割を果たす。
これらの対応戦略の選択は問題特性と要求品質によって異なり、一つのシステム内でも複数の戦略を階層的に組み合わせるのが普通である。例えば大規模な物流ルーティングエンジンは、まずヒューリスティックで初期経路を速く生成し、余裕時間内で局所探索によって改善した後、核心区間だけを精密アルゴリズムで再最適化する形で「速度-品質-正確性」を同時に満たす。
P=NP問題自体は依然として未解決であり、2000年にクレイ数学研究所が選定した七大ミレニアム難問(賞金100万ドル)の一つとして残っている。大多数の専門家はP≠NPを信じるがいずれも証明されておらず、自然証明(natural proofs)障壁・相対化(relativization)障壁など、既存の証明技法がなぜ通じないかに関するメタ理論だけが蓄積された状態である。もしP=NPが構成的に証明されれば、最適化・新薬設計・定理証明が革命的に容易になる一方、現代の公開鍵暗号の相当数が崩壊してセキュリティパラダイムの全面的再編が不可避となる。興味深いことに量子コンピューティング([[qubit]])はこの問題の解答ではない。量子アルゴリズムは素因数分解のような一部の問題を速く解くが、NP完全問題全般を多項式時間に解くという証拠はなく(Grover探索は平方根加速にとどまる)、そのため格子ベースなどの耐量子暗号([[post-quantum-cryptography]])の研究が別途進められる。
6. 考慮事項および示唆点
NP完全性はアルゴリズム設計の限界を規定すると同時に、その限界を工学的に迂回する戦略的思考を要求する。技術士の観点から以下を総合的に考慮しなければならない。
問題分類を設計初期に実施する。 最適化・スケジューリング・配置問題を受け取ったら、「これが既知のNP完全問題へ還元されるか」を最初に点検すべきである。NP完全と判明すれば「完璧な最適解法」要求を取り下げ近似・ヒューリスティックへ転じるのが資源浪費を防ぐ核心であり、逆に軽々しく「難しい」と断じて実際にはPに属する変種(2-SAT、MSTなど)を見逃すことも警戒すべきである。分類自体が設計品質を左右する。
正確性・時間・普遍性のトレードオフを要件に合わせる。 入力規模が小さく正確性が絶対的なら分枝限定やILP/SATソルバで正確解を、大規模リアルタイム環境なら近似比が保証されたアルゴリズムを、品質保証より平均性能が重要ならメタヒューリスティックを選ぶ。SLA・コスト・安全性要求に応じてこの均衡点を明示的に文書化し、「十分に良い解」の受容基準を利害関係者と合意することが失敗を減らす。
擬多項式とパラメータ化を積極的に活用する。 0/1ナップサックのように数値範囲が限定的なら擬多項式DPが現実的解法になり、被覆サイズ・木幅のような構造的パラメータが小さければFPTアルゴリズムが事実上多項式時間のように動作する。「NP完全=解けない」という二分法を捨て、実際の入力の特性(値の大きさ、構造的疎性)を分析して隠れた多項式時間性を発掘する洞察が高級な設計能力である。
暗号安全性の仮定を理解し転換に備える。 多くの公開鍵暗号の安全性は特定問題の計算的難解性の仮定に依存し、これはP≠NPというより大きな前提の上に立つ。アルゴリズムの画期的進展や量子コンピューティングの発展がこの仮定を揺るがしうるので、セキュリティアーキテクチャは暗号俊敏性(crypto-agility)を備え、耐量子暗号への移行経路を予め確保すべきである。難解性仮定の変化を追跡することは長期セキュリティ戦略の一部である。
ヒューリスティック解の品質を検証・監視する。 保証のないヒューリスティックを運用に投入するときは、下界・上界(例: LP緩和下界)に対する最適性ギャップを推定し、入力分布の変化に伴う品質低下を常時観測すべきである。「速い答え」が「誤った答え」にならないよう、近似解の品質指標をサービス監視体系に含め、閾値超過時により精密なアルゴリズムへ自動転換する設計が信頼性を高める。
参考資料
- S. A. Cook, "The Complexity of Theorem-Proving Procedures", STOC 1971. https://dl.acm.org/doi/10.1145/800157.805047
- R. M. Karp, "Reducibility Among Combinatorial Problems", 1972. https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9
- M. R. Garey, D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness", W. H. Freeman, 1979. https://www.google.com/books/edition/Computers_and_Intractability/fyVtp3EMxasC
- Clay Mathematics Institute, "P vs NP Problem". https://www.claymath.org/millennium/p-vs-np/
一言まとめ: P対NP問題は「検証が容易な問題(NP)は解くのも容易か(P)」を問う未解決難問であり、NP完全性は多項式時間還元とクック・レビンの定理を通じて、NPのすべての問題が帰着する「最も難しい」問題を一つの運命共同体として束ねる。ある問題がNP完全と判明すれば、完璧な最適解法の代わりに近似・ヒューリスティック・パラメータ化・特殊入力戦略へ転換すべきであり、この分類とトレードオフの判断が設計品質と暗号安全性戦略の核心である。