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と呼ばれる。
たとえば、非常に大きな数の因数を一から探すことは難しくても、候補となる二つの数を渡されれば、掛け算によって正しい因数分解かどうかを確認できる。
重要なのは、NPは「計算不可能」という意味ではないことだ。時間を十分に使えば全探索できる有限問題もある。また、小さな入力なら現実時間で解けることもある。問題となるのは、入力が大きくなったときの計算量の増え方である。
PとNPの比較
| 項目 | P | NP |
|---|---|---|
| 基本的な意味 | 多項式時間で解ける | Yesの証拠を多項式時間で検証できる |
| 解の探索 | 効率的な手続がある | 効率的な手続があるとは限らない |
| 解の検証 | 効率的 | 効率的 |
| 代表例 | 素数判定、最短経路 | SAT、ハミルトン閉路 |
| 未解決点 | Pの問題はNPにも属する | NPのすべてがPにも属するか不明 |
Pの問題は、証拠を渡されなくても効率よく解ける。したがって、Pの問題はNPの検証条件も満たす。
この包含関係は次のように表される。
P ⊆ NP
未解決なのは、この包含が真に狭いのか、それとも両者が一致するのかである。
P＝NPは証明されていない
P vs NP問題は、PとNPが等しいかを問う。
- P＝NPなら、正解を効率よく検証できる問題は、すべて効率よく解ける
- P≠NPなら、検証は効率的でも、解を作る一般的な効率手続が存在しない問題がある
現在、どちらも証明されていない。一般にはP≠NPだろうと予想されているが、予想と証明は別である。
NP完全問題とは何か
NP完全問題は、NPに属する問題のうち、NPのすべての問題を多項式時間で変換できる問題である。
代表例はSAT、特に3-SATだ。もしNP完全問題の一つに多項式時間アルゴリズムが見つかれば、すべての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の両側から特徴づけられる問題として注目され、その後AKS素数判定法によりPに属することが示された。検証しやすい特徴づけを見つけることが、効率的な判定手続につながる場合がある。ただし、NP ∩ coNPのすべてがPに入るかは未解決である。
TimeとSpaceは日常語ではない
計算量理論でいうTimeは、処理に何秒かかったかではなく、停止までの計算ステップ数である。Spaceは物理的な部屋の広さではなく、計算中に同時保持するメモリ量を指す。
Timeは一度使ったステップを再利用できない。一方、Spaceは同じ記憶領域を上書きして再利用できる。この違いから、時間計算量と空間計算量には別々のクラスがある。
入力から答えまでの分岐が多い問題を考えるときは、「時間が足りない」のか、「同時に保持する空間が足りない」のかを分ける必要がある。
経営でPとNPをどう読むか
現実の事業を数学上のPやNPにそのまま分類できるわけではない。ただし、探索と検証を分ける考え方は経営にも使える。
たとえば、売れる商品をゼロから発見することは難しくても、すでに売れている商品が利益条件を満たしているかは検証できる。最良の組織構造を一から探索することは難しくても、提示された組織案が予算、法令、納期の制約を満たすかは確認できる。
このとき必要なのは、すべての可能性を探索することではない。
- 何をYesとするかを定義する
- 検証可能な証拠を決める
- 絶対に満たすHard条件を固定する
- 衝突する候補を枝切りする
- 十分な解を得た時点で停止する
P vs NPから得られる実務上の示唆は、「難しい問題をすべて解け」ということではない。解の構築と検証を分離し、有限資源で停止できる問題へ変換することである。
『P vs NP経営』の詳細はこちら https://link.amazon/B04IEdYsn