計算複雑性理論の未解決問題：P vs NP問題

計算複雑性理論は「どんな問題が効率的に解けるか？」を数学的に分類する分野です。その中心にある最大の未解決問題が「P=NPか？」です。

---

P（Polynomial time）

• 定義：入力サイズに対して多項式時間で決定できる問題のクラス
• 意味：現実的な計算機（決定性チューリングマシン）で、現実的な時間内に解ける問題
• 例：
  • 整数のソート
  • 最短経路の計算（ダイクストラ法など）
  • 有向グラフにサイクルがあるか判定

---

NP（Nondeterministic Polynomial time）

• 定義：「与えられた解が正しいか」を多項式時間で検証できる問題のクラス
• 意味：解が与えられたとき、それが正しいかどうかはすぐにチェックできる
• 例：
  • ナップサック問題
  • 巡回セールスマン問題（TSP）
  • 数独

P ⊆ NP（Pの問題はすべてNPでもある）

---

NP完全（NP-complete）

• 定義：NPの中でも、最も難しい部類。すべてのNP問題が多項式時間でこの問題に帰着できる
• 意味：この問題を多項式時間で解けたら、NPのすべての問題が解けることになる
• 条件（両方満たす）：
  1. NPに属する
  2. すべてのNP問題を多項式時間でこの問題に変換可能（NP困難）
• 例：
  • 充足可能性問題（SAT）
  • グラフ彩色問題（3-Coloring）
  • ハミルトン路の存在判定

---

NP困難（NP-hard）

• 定義：すべてのNP問題を多項式時間で帰着できるが、自分自身はNPに属さないかもしれない
• 意味：最悪クラスの難しさ。解の検証すら多項式時間でできるとは限らない
• 例：
  • 停止問題（決定不能）
  • 一部の最適化問題（例：TSPの最小コスト解を求める問題）

NP完全 ⊂ NP困難

---

P vs NP問題：計算理論最大の未解決問題

「P = NP か？」 これは「すべてのNP問題は、多項式時間で解けるのか？」という問いです。

• P = NPなら：数独や巡回セールスマン問題など、今まで“難しい”とされてきた問題が、現実的な時間で解けることになる
• P ≠ NPなら：一部の問題は、解の検証は簡単でも、解くのは本質的に難しい

現在も未解決。多くの研究者は「P ≠ NP」と考えていますが、決定的な証明は存在しません。

---

まとめ

• P：効率的に解ける問題
• NP：効率的に「検証」できる問題
• NP完全：NPで最も難しい問題
• NP困難：NPのすべてを含む最悪クラス

「P=NPか？」は、計算理論・暗号・AI・最適化など現代社会の根幹に関わる最大の未解決問題です。今後の進展に注目しましょう。