2.1 P 的定義與例子#

概念說明#

P（Polynomial time）是所有「可在多項式時間內被決定性圖靈機解決的決策問題」構成的類別。正式地說：

語言 L 屬於 P，若且唯若存在一台決定性圖靈機 M 與多項式 p，使得對所有輸入 x，M 在 p(|x|) 步內停機，且 M(x) = 是 ⟺ x ∈ L。

幾個重要的直覺補充：

P 是「實際可解」的理論近似。P 中的問題，我們認為有「快速」演算法；不在 P 中（或懷疑不在 P 中）的問題，我們只能靠窮舉或特殊技巧。
P 針對決策問題，但對最佳化問題有自然的對應：把「求最佳解」變成「是否存在目標值 ≤ K 的解」，兩者的複雜度通常相距一個多項式因子。
P 對許多運算封閉：交集、聯集、補集（P 對補集封閉，這點與 NP 不同且意義重大）、以及多項式時間的函數合成。

P 中的常見問題族譜：

數值類：最大公因數（歐幾里得演算法 O(L²)，L 為位元數）、質數判定（AKS，O(L⁶) 等級）、矩陣相乘（O(n^2.37)）。
排序搜尋類：排序 O(n log n)、二分搜尋 O(log n)。
圖論類：最短路徑（Dijkstra O((V+E) log V)）、最小生成樹（Kruskal O(E log E)）、連通性（BFS/DFS O(V+E)）、最大流（多項式時間）。
字串類：字串比對（KMP O(n+m)）、最長共同子序列（DP，O(nm)）。

注意一個容易被誤解的點：「還沒找到多項式時間演算法」不代表「證明不存在」。事實上我們幾乎無法證明任何自然問題不在 P 中；NP-complete 問題的難度是一種「若 P ≠ NP 則難」的條件性陳述。

演算法步驟：以最大公因數為例走一遍「P 問題」的標準流程#

問題規格：輸入兩個整數 a, b（以位元數 L 表示大小），判斷 gcd(a,b) 是否為 1（互質判定，是決策問題）。
演算法：歐幾里得輾轉相除——gcd(a, b) = gcd(b, a mod b)，直到 b = 0。
正確性：任何 a、b 的公因數也是 b 與 a mod b 的公因數，反之亦然，因此遞迴保持 gcd 不變。
複雜度：每次迭代至少讓較大數減半（兩輪迭代必定），故迭代數為 O(L)，每次模運算 O(L²)，總計 O(L³) 以下——多項式時間。

Python 程式碼範例#

import math, random, time

def gcd_steps(a, b):
    """歐幾里得演算法，回傳 gcd 與迭代次數"""
    steps = 0
    while b:
        a, b = b, a % b
        steps += 1
    return a, steps

def coprime_decision(a, b):
    """決策問題：a 與 b 是否互質"""
    g, _ = gcd_steps(a, b)
    return g == 1

# 實驗：迭代次數與位元數的關係（Lamé 定理：迭代數 ≤ 約 5 × 位元數）
print(f"{'位元數':>6} {'平均迭代數':>10} {'理論上界 5L':>12}")
for bits in [16, 32, 64, 128, 256]:
    total = 0
    trials = 200
    for _ in range(trials):
        a = random.getrandbits(bits) | 1
        b = random.getrandbits(bits) | 1
        _, s = gcd_steps(a, b)
        total += s
    print(f"{bits:>6} {total/trials:>10.1f} {5*bits:>12}")

# 大數實測：256 位元的互質判定瞬間完成
a = random.getrandbits(256) | 1
b = random.getrandbits(256) | 1
t0 = time.time()
print("互質?", coprime_decision(a, b), f"耗時 {time.time()-t0:.6f} 秒")

複雜度分析#

歐幾里得演算法：由 Lamé 定理，迭代次數不超過約 5 倍的位元數（與費波那契數列的聯繫），每次取模在位元模型下為 O(L²)，總複雜度 O(L³) —— 是輸入位元數的多項式。
這個例子示範了分析 P 問題的完整模板：形式化規格 → 演算法 → 正確性論證 → 位元模型下的複雜度分析。

練習#

證明：若 L₁, L₂ ∈ P，則 L₁ ∩ L₂ ∈ P 且 L₁ ∪ L₂ ∈ P。
修改上面的程式，改為判定「a 是否為完全平方數」，使用牛頓法或整數平方根，並分析其對位元數的複雜度。
下面的問題哪些屬於 P？請說明理由：(a) 判斷一個 n×n 矩陣是否對稱；(b) 判斷一個整數列表是否能分成兩半使總和相等；(c) 給定 n 個整數，判斷是否存在三個數之和為 0（提示：排序後可用雙指標做到 O(n²)）。