P vs NP Problem

P vs NP 問題探討問題解方的難度

@ 技術討論

前言

P 與 NP 用來描述解決問題的難度所需的時間為：polynomial time 或 non-deterministic polynomial time。

將問題分類為 P 或 NP，有助於理解一個問題是否有可能在合理的時間內被解決——即執行時間不會隨著輸入規模的增長而爆炸性膨脹，歷史上有許多原本只知道屬於 NP 的問題，後來被找到了 Polynomial time 的演算法，從而被證實其實也屬於 P 問題，像是：質數判定🔗。但目前沒有證據可證明所有 NP 問題是 P 問題。

P vs NP

  • P 問題
    • 可快速解決
    • 快速驗證
  • NP 問題
    • 不確定能否快速解決
    • 快速驗證

快速在這裡指「問題能不能處理任何輸入時在 polynomial time 時間內被解決」，像是 Big O🔗 表示來說：

  • 常數時間：O(1)
  • 對數時間：O(log n)
  • 線性時間：O(n)
  • 線性對數時間：O(n log n)
  • 平方時間：O(n²)
  • 立方時間：O(n³)

P 問題範例：排序

給定 [3, 1, 4, 1, 5, 9]，排序由小到大。

  • 解決：直接用排序演算法（例如 merge sort🔗），O(n log n)。
  • 驗證：掃一遍確認每個數 ≤ 下一個數，O(n)。

NP 問題範例：子集合加總（Subset Sum）

給定 [3, 7, 1, 8, 5]，有沒有某個子集合的總和恰好等於 14？

  • 解決：試遍所有子集合，有 2ⁿ 種可能，只要輸入 n 一大就爆炸。目前沒有已知的 polynomial time 解法。
  • 驗證：假設是 [1, 5, 8]，只要運算一下：1+5+8=14，O(n)。

Reducibility 歸約

如果問題 A 可以轉換成問題 B，那 B 至少跟 A 一樣難

想像你有一台完美的翻譯器（歸約函式），能將「法文問題 (A)」轉換為「英文問題 (B)」：

因為只要有翻譯器，任何法文問題都能變成英文問題來解；所以只要能解英文問題，就等於能解所有的法文問題，代表英文問題的難度涵蓋了法文問題。

Terminal window
# A 可以在「polynomial time」內轉歸約為 B
A ≤p B

NPC NP-Complete

NP 當中最難的問題
  • 是 NP 問題
  • 任何一個 NP 問題，都可以在 polynomial time 內歸約成這個問題的形式

要釐清 P 是否等於 NP 可以透過解決 NP-Complete 問題來得出答案，因為所有 NP 問題都能 Reduce 為 NPC。

NP-Complte 問題範例：SAT（Boolean Satisfiability Problem）

所有 NP 問題 ≤p SAT

有沒有一種 A、B、C 的 true/false 組合，能讓整個公式成立？

(A ∨ ¬B) ∧ (¬A ∨ C) ∧ (B ∨ ¬C)
  • 解決：最壞情況需要枚舉所有 2ⁿ 種組合，沒有已知的 polynomial time 解法。
  • 驗證：給定一組指派，代入計算即可在 O(n) 內確認。

總結

P = NP? 在於「能快速驗證答案」 是否等同於 「能快速找到答案」？

延伸閱讀