PとNPの違い｜解くことと検証することは同じか
PとNPの違いを一言で表すと、Pは効率よく解ける問題のクラス、NPは正解の候補を受け取れば効率よく検証できる問題のクラスである。
ここでいう「効率よく」とは、人間の感覚で速いという意味ではない。入力の大きさを \(n\) としたとき、必要な計算ステップ数が \(n^2\)、\(n^3\) などの多項式で抑えられることを指す。
Pとは何か
PはPolynomial Time、多項式時間の略である。決定性チューリングマシンが、多項式時間でYesまたはNoを判定できる問題がPに属する。
代表例には次のようなものがある。
- 数が素数かどうかの判定
- グラフ上の二点が接続されているかの判定
- 最短経路の計算
- 線形計画問題
手続が決まっており、同じ入力には同じ計算が進み、入力が大きくなっても必要ステップ数の増加を多項式で記述できる。
NPとは何か
NPはNondeterministic Polynomial Time、非決定性多項式時間の略である。
NPに属する問題では、答えがYesである場合、その証拠を受け取れば多項式時間で正しさを検証できる。この証拠はwitnessまたはcertificateと呼ばれる。
整数の素因数分解は、候補の因数を渡せば掛け算で正しさを多項式時間検証できる（Yes側はNPの検証条件を満たす）。NP完全だとは限らない。たとえば、非常に大きな数の因数を一から探すことは難しくても、候補となる二つの数を渡されれば、掛け算によって正しい因数分解かどうかを確認できる。
重要なのは、NPは「計算不可能」という意味ではないことだ。時間を十分に使えば全探索できる有限問題もある。また、小さな入力なら現実時間で解けることもある。問題となるのは、入力が大きくなったときの計算量の増え方である。
計算の「非対称性」
大きな2つの素数 A と Bについて
-
掛け算（検証）： A × B = N
-
簡単：桁数が増えても、小学校で習う筆算と同じ手順を行うだけ。桁数を n とすると、およそ n² 回程度の基本操作で一瞬で完了（多項式時間）。
-
-
因数分解（探す）： N → A × B
-
難しい：N だけを見せられても、A や Bの因数が何であるかの手がかりはない。最悪の場合、片っ端から数を割って試す（しらみつぶしに探す）必要があり、桁数が伸びると組み合わせの数が指数関数的に爆発（指数時間）。
-
PとNPの比較
| 項目 | P | NP |
|---|---|---|
| 基本的な意味 | 多項式時間で解ける | Yesの証拠を多項式時間で検証できる |
| 解の探索 | 効率的な手続がある | 効率的な手続があるとは限らない |
| 解の検証 | 効率的 | 効率的 |
| 代表例 | 素数判定、最短経路 | SAT、ハミルトン閉路 |
| 未解決点 | Pの問題はNPにも属する | NPのすべてがPにも属するか不明 |
Pの問題は、証拠を渡されなくても効率よく解ける。したがって、Pの問題はNPの検証条件も満たす。
この包含関係は次のように表される。
P ⊆ NP
未解決なのは、この包含が真に狭いのか、それとも両者が一致するのかである。
P＝NP? P≠NP?
P vs NP問題は、PとNPが等しいかを問う。
- P＝NPなら、正解を効率よく検証できる問題は、すべて効率よく解ける
- P≠NPなら、検証は効率的でも、解を作る一般的な効率手続が存在しない問題がある
現在、どちらも証明されていない。一般にはP≠NPだろうと予想されている。
Hardness vs Randomness（難しさと乱数）の系譜では、Russell Impagliazzo（ラッセル・インパリアッツォ、1963–）と Avi Wigderson（アヴィ・ウィグダーソン、1956–）の1997年の結果のように、指数時間クラス E が十分強い回路下界を持つといった適切な難しさ（Hardness）を仮定すると、BPP／RPを決定的多項式時間でシミュレートできる、と示される場合がある。これは素のP≠NPからの導出ではない。
そこから類推して、P≠NPは一定の論理的閾値として、計算を効率化することに一役買っているのではないかと筆者は予想している。これは証明された事実ではない。予想と証明は別である。
NP-completeとは何か
NP-complete（NP完全）問題とは、NPに属し、かつNPの任意の問題から多項式時間で還元できる問題である（NP-hard かつ NP）。
直感的な説明としては、NPは「最悪だと計算が爆発し、全宇宙の粒子を全て使っても解けない問題になる」という見方がある。定義そのものは、上の還元によって与えられる。
代表例はSAT、とりわけ3-SATである。平面グラフの3彩色もNP完全だが、3-SATそのものではない（関連する別問題である）。Stephen A. Cook（スティーブン・A・クック、1939–）の1971年の結果と、独立に示された Leonid A. Levin（レオニード・A・レヴィン、1948–）の議論（いわゆる Cook–Levin 定理）により、SATはNP完全の代表となる。もしNP-complete問題の一つに多項式時間アルゴリズムが見つかれば、すべてのNP問題を多項式時間で解けることになり、P＝NPが成立する（しかし発見されてはいない）。
逆に、NP完全問題の一つでもPに属さないことを証明できれば、P≠NPが成立する。
coNPとは何か
NPが「Yesであることを短い証拠で検証できる」問題なら、coNPは「Noであることを短い証拠で検証できる」問題である。
SATは、条件を満たす真偽割当を一つ提示すればYesを検証できる。対になるトートロジー判定では、論理式がすべての割当で真かを問う。このように、あることの証明と、ないことの証明は対称とは限らない。
Pでは、YesかNoかを多項式時間で直接判定できるため、反対側も同じ時間で判定できる。一方、NPでYesの証拠が短いからといって、Noの証拠まで短いとは限らない。
| クラス | 多項式時間で検証できるもの |
|---|---|
| NP | Yesの証拠 |
| coNP | Noの証拠 |
| NP ∩ coNP | YesとNoの両方の証拠 |
| P | YesとNoを直接判定 |
素数判定は、かつてNPとcoNPの両側から特徴づけられる問題として注目され、その後 Manindra Agrawal（マニンドラ・アグラワル、1966–）、Neeraj Kayal（ニーラジ・カヤル、1979–）、Nitin Saxena（ニティン・サクセナ、1981–）による AKS素数判定法（2002年）によりPに属することが示された。検証しやすい特徴づけを見つけることが、効率的な判定手続につながる場合がある。
TimeとSpace
計算量理論でいうTimeは、処理に何秒かかったかではなく、停止までの計算ステップ数である。Spaceは物理的な部屋の広さではなく、計算中に同時保持するメモリ量を指す。
Timeは一度使ったステップを再利用できない。一方、Spaceは同じ記憶領域を上書きして再利用できる。この違いから、時間計算量と空間計算量には別々のクラスがある。
入力から答えまでの分岐が多い問題を考えるときは、「時間が足りない」のか、「同時に保持する空間が足りない」のかを分ける必要がある。
経営でPとNPをどう応用するか
現実の事業を数学上のPやNPにそのまま分類できるわけではない。経営へ応用するなら、探索と検証を分ける考え方である。これは定理の適用ではなく、手続の写像である。
たとえば、売れる商品をゼロから発見することは難しくても、すでに売れている商品が利益条件を満たしているかは検証できる。最良の組織構造を一から探索することは難しくても、提示された組織案が予算、法令、納期の制約を満たすかは確認できる。
このとき必要なのは、すべての可能性を探索することではない。
- 何をYesとするかを定義する
- 検証可能な証拠（witness）を決める
- 充足可能性条件を探索する
- 衝突する候補を枝切りする
- 全探索を仕切る前に、満足いく解を得た時点で停止する（Herbert A. Simon（ハーバート・A・サイモン、1916–2001）のsatisficing／満足化）
P vs NPから得られる実務上の示唆は、「難しい問題をすべて解け」ということではない。解の構築と検証を分離し、有限資源で停止できる問題へ変換することである。
『P vs NP経営』の詳細はこちら https://link.amazon/B04IEdYsn