1971 - Cook 的 NP-完全理論（計算複雜度的分水嶺）#

from itertools import product

# 1) SAT：暴力解（2^n，指數時間）
def sat_brute(clauses, n_vars):
    """clauses: 子句列表（每個子句是變數索引列表，正=xi，負=¬xi）"""
    for assign in product([False, True], repeat=n_vars):
        if all(any(assign[abs(l)-1] == (l > 0) for l in clause) for clause in clauses):
            return assign
    return None

# 2) 3-SAT 的例子（3 個文字一個子句）
clauses = [[1, 2, 3], [-1, 2, 3], [1, -2, 3], [-1, -2, -3]]
print("3-SAT 的暴力解（2^n 時間）：")
for n_vars in [3, 5]:
    if n_vars == 3:
        c = clauses
    else:
        c = clauses + [[2, 4, 5], [-3, -4, -5], [1, 4, -5], [-2, -5, 4]]
    import time
    import itertools as it
    result = sat_brute(c, n_vars)
    n_combos = 2**n_vars
    print(f"  {n_vars} 個變數，{len(c)} 個子句：{n_combos} 種組合")
    if result:
        print(f"    可滿足！指派 = {[int(v) for v in result]}")
    else:
        print(f"    不可滿足")

# 3) 指數爆炸的驗證（2^n 的成長）
print("\n指數爆炸（2^n 的成長）：")
for n in [10, 20, 30, 40, 50]:
    print(f"  n = {n}: 2^n = {2**n:>15} 種組合")
    if n == 30:
        print(f"    （10 億種——已不可行）")
    if n == 50:
        print(f"    （10^15 種——即使每秒 10 億次也要 12 天）")

# 4) 歸約：3-SAT → 頂點覆蓋（Karp 1972 的歸約之一）
print("\n歸約（3-SAT → 頂點覆蓋，Karp 1972）：")
# 對每個子句建一個三角形，變數對建一對邊
def reduce_3sat_to_vc(clauses, n_vars):
    """歸約：多項式時間的圖構造"""
    edges = []
    node_id = n_vars   # 子句節點從 n_vars 開始
    clause_nodes = []
    for i, clause in enumerate(clauses):
        a, b, c = node_id, node_id+1, node_id+2
        clause_nodes.append((a, b, c))
        edges += [(a,b), (b,c), (a,c)]   # 三角形
        node_id += 3
    # 變數節點與子句節點的連接
    for i, clause in enumerate(clauses):
        for j, lit in enumerate(clause):
            var = abs(lit) - 1
            edges.append((clause_nodes[i][j], var))
    k = n_vars + len(clauses)   # 覆蓋大小
    return edges, k

edges, k = reduce_3sat_to_vc(clauses, 3)
print(f"  3 個子句 → 圖：{len(edges)} 條邊，覆蓋大小 k = {k}")
print(f"  構造時間 = O(子句數 × 文字數)（多項式 ✓）")
print("  → 3-SAT 可滿足 ⟺ 圖有大小 k 的頂點覆蓋")
print("  → 解決頂點覆蓋就能解決 3-SAT（NP-完全的傳播）")

# 5) P vs NP 的意義
print("\nP vs NP（千禧年問題，1971 Cook）：")
print("  P：多項式時間可解（排序、最短路徑）")
print("  NP：多項式時間可驗證（SAT、TSP）")
print("  P ⊆ NP；問題：P = NP？")
print("  若 P = NP：密碼學崩潰（RSA 可破）、最佳化全解")
print("  若 P ≠ NP：有些問題原理上無法快速求解（多數人相信）")
print("  → 這是計算理論最重要的未解問題（100 萬美元獎金）")

3-SAT 的暴力解（2^n 時間）：
  3 個變數，4 個子句：8 種組合
    可滿足！指派 = [0, 0, 1]
  5 個變數，8 個子句：32 種組合
    可滿足！指派 = [0, 0, 1, 1, 0]

指數爆炸（2^n 的成長）：
  n = 10: 2^n =            1024 種組合
  n = 20: 2^n =       1048576 種組合
  n = 30: 2^n =    1073741824 種組合
    （10 億種——已不可行）
  n = 40: 2^n = 1099511627776 種組合
  n = 50: 2^n = 1125899906842624 種組合
    （10^15 種——即使每秒 10 億次也要 12 天）

歸約（3-SAT → 頂點覆蓋，Karp 1972）：
  3 個子句 → 圖：24 條邊，覆蓋大小 k = 7
  構造時間 = O(子句數 × 文字數)（多項式 ✓）
  → 3-SAT 可滿足 ⟺ 圖有大小 k 的頂點覆蓋
  → 解決頂點覆蓋就能解決 3-SAT（NP-完全的傳播）

P vs NP（千禧年問題，1971 Cook）：
  P：多項式時間可解（排序、最短路徑）
  NP：多項式時間可驗證（SAT、TSP）
  P ⊆ NP；問題：P = NP？
  若 P = NP：密碼學崩潰（RSA 可破）、最佳化全解
  若 P ≠ NP：有些問題原理上無法快速求解（多數人相信）
  → 這是計算理論最重要的未解問題（100 萬美元獎金）