談計算複雜度理論（Computational Complexity Theory）

「計算複雜度理論（Computational Complexity Theory）」研究的是：

🔎 一個問題「需要多少資源」才能被解決？

• ⏳ 時間（Time Complexity）
• 💾 空間（Space Complexity）
• 📡 隨機性（Randomness）
• 🔐 交互次數（Interactive rounds）
• ⚛️ 量子資源（Quantum resources）

這門理論是現代密碼學、區塊鏈、量子計算與人工智慧的數學基礎。

一、核心問題

計算複雜度理論關心三個核心問題：

1. 這個問題是否「可解」？
2. 如果可解，能否「有效率」地解？
3. 如果無法有效率解，是否可用於密碼學？

二、時間複雜度（Time Complexity）

使用 Big-O 表示法

例如：

• 排序：O(n log n)
• 暴力破解密碼：O(2ⁿ)

三、複雜度類別（Complexity Classes）

1️⃣ P 類（Polynomial Time）

可在多項式時間內解決

例：

• 最短路徑
• 最大流
• 排序

2️⃣ NP類（Nondeterministic Polynomial）

問題本身難，但「答案可快速驗證」

例：

• 數獨
• 哈密頓路徑
• SAT 問題

3️⃣ NP-Complete

最難的 NP 問題

如果有一個 NP-complete 可被快速解決：

→ 所有 NP 問題都可快速解

著名問題：

• SAT
• 旅行推銷員問題（決定版）

4️⃣ NP-Hard

比 NP 還難（可能不可驗證）

四、P vs NP 問題

P 是否等於 NP？

這是數學七大千禧年問題之一。

若：

• P = NP → 密碼學崩潰
• P ≠ NP → 單向函數存在

目前主流相信：

P ≠ NP

五、空間複雜度（Space Complexity）

• L（Log Space）
• PSPACE
• EXPSPACE

重要關係：

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME

六、隨機複雜度

BPP（Bounded-error Probabilistic Polynomial）

允許隨機演算法

應用：

• Miller-Rabin 質數測試
• 密碼學

七、量子複雜度

量子計算改變複雜度結構。

重要類別：

• BQP（量子多項式時間）
• QMA（量子 NP）

例子：

• Peter Shor 的演算法可在量子電腦上分解大數
• 影響 RSA

八、複雜度與密碼學

密碼學依賴「計算困難性假設」：

九、電路複雜度

研究：

最少需要多少邏輯閘才能實現函數？

例如：

• AC⁰
• NC
• P/poly

這與：

• 雜湊函數
• 同態加密
• 零知識證明

高度相關

十、計算層級結構

著名定理：

時間層級定理（Time Hierarchy Theorem）

告訴我們：

更多時間 → 能解更多問題

十一、資訊論 vs 計算複雜度

資訊論：

• 是否「理論上可解」

計算複雜度：

• 是否「實務上可算」

這也是你之前提到「秘密計算」與「資訊宇宙論」的分界點：

宇宙可能是可計算的

但不一定是可有效率計算的

十二、現代發展前沿

1. 平均情況複雜度
2. 難例生成（Worst-case to Average-case）
3. 零知識證明
4. 證明 vs 計算（Proof Complexity）
5. 格複雜度（Lattice hardness）

十三、哲學層面

計算複雜度理論其實在問：

「宇宙是否存在不可快速知道的真理？」

例如：

• 真理存在
• 但計算資源不允許你知道

這直接連到：

• Gödel 不完備性
• 計算宇宙觀
• 黑洞資訊悖論

十四、總結結構圖

可計算性（Turing）
      ↓
複雜度理論
      ↓
P vs NP
      ↓
密碼學
      ↓
量子計算
      ↓
宇宙是否可有效率模擬？