跳转至

计算复杂性

概述

计算复杂性理论研究的不是"能否计算"，而是"计算需要多少资源"。即使问题可判定，其所需的时间或空间资源也可能使其在实际中不可解。

1. 复杂性类基础

1.1 时间复杂性

定义：图灵机 \(M\) 的时间复杂度 \(t(n)\) 是 \(M\) 在所有长度为 \(n\) 的输入上的最大运行步数。

\[ \text{TIME}(t(n)) = \{L \mid \text{存在 } O(t(n)) \text{ 时间的确定性TM判定 } L\} \]

1.2 基本复杂性类

\[ \textbf{P} = \bigcup_{k \geq 0} \text{TIME}(n^k) \]

P类：多项式时间可判定的语言。代表"高效可解"的问题。

\[ \textbf{NP} = \bigcup_{k \geq 0} \text{NTIME}(n^k) \]

NP类：非确定性多项式时间可判定的语言。

等价定义：\(L \in \textbf{NP}\) 当且仅当存在多项式时间验证器 \(V\) 和多项式 \(p\)，使得：

\[ w \in L \iff \exists c \; (|c| \leq p(|w|) \wedge V(w, c) = \text{accept}) \]

其中 \(c\) 称为证书（certificate）或见证（witness）。

NP问题示例

合数问题 COMPOSITES：给定整数 \(n\)，\(n\) 是合数吗？

  • 证书：\(n\) 的一个非平凡因子 \(d\)
  • 验证：检查 \(1 < d < n\) 且 \(d \mid n\)，这在多项式时间内完成

注意：COMPOSITES（以及PRIMES）实际上也在 P 中（AKS素性测试，2002年）。

1.3 co-NP

\[ \textbf{co-NP} = \{L \mid \overline{L} \in \textbf{NP}\} \]
  • \(\textbf{P} \subseteq \textbf{NP} \cap \textbf{co-NP}\)
  • 一般认为 \(\textbf{NP} \neq \textbf{co-NP}\)
graph TB
    subgraph "复杂性类层次（假设P≠NP）"
        P["P"]
        NPI["NP-intermediate"]
        NPC["NP-complete"]
        NP["NP"]
    end
    P --> NPI --> NPC
    P --> NP
    NPC --> NP

2. P vs NP 问题

2.1 问题陈述

\[ \textbf{P} \stackrel{?}{=} \textbf{NP} \]

这是计算机科学（也是数学）中最重要的开放问题之一，是Clay数学研究所七个千禧年大奖问题之一。

2.2 直觉理解

  • P：可以快速求解的问题
  • NP：可以快速验证的问题
  • P vs NP：快速验证是否意味着快速求解？

大多数计算机科学家相信 \(\textbf{P} \neq \textbf{NP}\)。

2.3 如果 P = NP

若 \(\textbf{P} = \textbf{NP}\)，则：

  • 所有NP问题都可以多项式时间求解
  • 现代密码学（基于因式分解、离散对数等困难假设）将崩溃
  • 优化问题（调度、路由等）将变得"容易"
  • 数学定理的发现将变得容易（验证 \(\to\) 搜索）

3. NP完全性

3.1 多项式时间归约

定义：\(A \leq_p B\)（\(A\) 多项式时间归约到 \(B\)），若存在多项式时间可计算函数 \(f\)，使得：

\[ w \in A \iff f(w) \in B \]

性质：

  • 若 \(A \leq_p B\) 且 \(B \in \textbf{P}\)，则 \(A \in \textbf{P}\)
  • 传递性：\(A \leq_p B\) 且 \(B \leq_p C \implies A \leq_p C\)

3.2 NP完全的定义

语言 \(L\) 是 NP完全的，若：

  1. \(L \in \textbf{NP}\)
  2. \(\forall A \in \textbf{NP}, A \leq_p L\)（NP-hard）

NP完全问题是NP中"最难"的问题。若任何一个NP完全问题有多项式算法，则 \(\textbf{P} = \textbf{NP}\)。

3.3 Cook-Levin定理

定理（Cook 1971, Levin 1973）：SAT 是NP完全的。

SAT（布尔可满足性问题）：

  • 输入：布尔公式 \(\phi(x_1, x_2, \ldots, x_n)\)
  • 问题：是否存在变量赋值使 \(\phi\) 为真？

证明思路：

  1. SAT \(\in\) NP：给定赋值，可多项式时间验证
  2. NP-hard：对任意 NP 语言 \(A\)，将其非确定图灵机的计算过程编码为布尔公式
    • 用变量表示TM配置（状态、带内容、头位置）
    • 转移函数编码为子句
    • 接受条件编码为子句

4. 经典NP完全问题

4.1 3-SAT

\[ \phi = (x_1 \vee \bar{x}_2 \vee x_3) \wedge (\bar{x}_1 \vee x_2 \vee x_4) \wedge \cdots \]

每个子句恰好3个文字的合取范式(CNF)的可满足性。

归约：SAT \(\leq_p\) 3-SAT（将长子句拆分，引入辅助变量）

4.2 团问题（CLIQUE）

  • 输入：图 \(G = (V, E)\)，正整数 \(k\)
  • 问题：\(G\) 是否包含大小为 \(k\) 的团（完全子图）？

归约：3-SAT \(\leq_p\) CLIQUE

对于 \(m\) 个子句的3-SAT实例，构造图 \(G\)： - 每个子句的每个文字是一个顶点 - 连边条件：不在同一子句中，且不互补 - 设 \(k = m\)

4.3 顶点覆盖（VERTEX COVER）

  • 输入：图 \(G = (V, E)\)，正整数 \(k\)
  • 问题：是否存在 \(S \subseteq V\)，\(|S| \leq k\)，使得每条边至少有一个端点在 \(S\) 中？

归约：CLIQUE \(\leq_p\) VERTEX COVER

图 \(G\) 有大小为 \(k\) 的团 \(\iff\) 补图 \(\overline{G}\) 有大小为 \(|V| - k\) 的顶点覆盖。

4.4 哈密顿回路（HAMILTONIAN CYCLE）

  • 输入：图 \(G\)
  • 问题：\(G\) 是否包含经过每个顶点恰好一次的回路？

4.5 旅行商问题（TSP）

  • 输入：\(n\) 个城市间的距离矩阵，预算 \(B\)
  • 问题：是否存在总距离 \(\leq B\) 的回路访问所有城市？

归约：HAMILTONIAN CYCLE \(\leq_p\) TSP

4.6 归约关系图

graph TD
    SAT[SAT] --> 3SAT[3-SAT]
    3SAT --> CLIQUE[团问题]
    3SAT --> IS[独立集]
    CLIQUE --> VC[顶点覆盖]
    IS --> VC
    3SAT --> 3COLOR[3-着色]
    3SAT --> SUBSET[子集和]
    SUBSET --> KNAPSACK[背包问题]
    SUBSET --> PARTITION[划分问题]
    VC --> HC[哈密顿回路]
    HC --> TSP[旅行商问题]
    3SAT --> DS[支配集]

5. NP完全问题列表

问题 类别 描述
SAT 逻辑 布尔公式可满足性
3-SAT 逻辑 3-CNF可满足性
CLIQUE 图论 图中最大团
VERTEX COVER 图论 最小顶点覆盖
INDEPENDENT SET 图论 最大独立集
3-COLORING 图论 3色着色
HAMILTONIAN CYCLE 图论 哈密顿回路
TSP 优化 旅行商问题
SUBSET SUM 数论 子集和问题
KNAPSACK 优化 0-1背包问题
SET COVER 集合 最小集合覆盖
PARTITION 数论 等分划分

Karp在1972年的经典论文中列出了21个NP完全问题，奠定了NP完全性理论的基础。

6. PSPACE

6.1 定义

\[ \textbf{PSPACE} = \bigcup_{k \geq 0} \text{SPACE}(n^k) \]

6.2 层次关系

\[ \textbf{P} \subseteq \textbf{NP} \subseteq \textbf{PSPACE} \subseteq \textbf{EXPTIME} \]

由时间层次定理：\(\textbf{P} \neq \textbf{EXPTIME}\)，但我们不知道中间的包含关系是否严格。

Savitch定理：

\[ \text{NSPACE}(s(n)) \subseteq \text{SPACE}(s(n)^2) \]

推论：\(\textbf{NPSPACE} = \textbf{PSPACE}\)

6.3 PSPACE完全问题

TQBF（完全量化布尔公式）：

\[ \exists x_1 \forall x_2 \exists x_3 \cdots \phi(x_1, x_2, x_3, \ldots) \]

TQBF是PSPACE完全的（类似SAT对NP的地位）。

其他PSPACE完全问题：

  • 广义地理游戏（Generalized Geography）
  • 围棋（Go）的最优策略
  • 正则表达式等价性

7. 近似算法

7.1 动机

既然NP完全问题（很可能）没有多项式精确算法，我们能否在多项式时间内找到近似最优解？

7.2 近似比

对于最小化问题，算法 \(A\) 的近似比 \(\rho\) 满足：

\[ \frac{A(I)}{OPT(I)} \leq \rho \quad \text{对所有实例 } I \]

7.3 经典近似结果

问题 近似比 算法
顶点覆盖 2 贪心匹配
集合覆盖 \(\ln n\) 贪心
TSP（三角不等式） 1.5 Christofides
MAX-SAT 0.75 随机取整
背包问题 \(1 + \varepsilon\) FPTAS

7.4 不可近似性

PCP定理（Probabilistically Checkable Proofs）：

\[ \textbf{NP} = \textbf{PCP}[\log n, 1] \]

这意味着某些NP完全问题在 \(\textbf{P} \neq \textbf{NP}\) 假设下不能被近似到任意比：

  • MAX-3SAT：不能近似到优于 \(7/8\) 的比率
  • CLIQUE：不能近似到 \(n^{1-\varepsilon}\) 的比率
  • SET COVER：不能近似到优于 \(\ln n\) 的比率（除非 \(\textbf{P} = \textbf{NP}\)）

8. 复杂性类全景

graph TB
    subgraph "空间复杂性"
        L["L (对数空间)"]
        NL["NL"]
        PSPACE["PSPACE"]
    end
    subgraph "时间复杂性"
        P["P"]
        NP["NP"]
        coNP["co-NP"]
        EXP["EXPTIME"]
    end
    L --> NL --> P --> NP --> PSPACE --> EXP
    P --> coNP --> PSPACE

已知的严格包含：

  • \(\textbf{L} \subsetneq \textbf{PSPACE}\)（空间层次定理）
  • \(\textbf{P} \subsetneq \textbf{EXPTIME}\)（时间层次定理）
  • \(\textbf{NL} \subsetneq \textbf{PSPACE}\)

主要开放问题：

  • \(\textbf{P} \stackrel{?}{=} \textbf{NP}\)
  • \(\textbf{NP} \stackrel{?}{=} \textbf{co-NP}\)
  • \(\textbf{P} \stackrel{?}{=} \textbf{PSPACE}\)
  • \(\textbf{NP} \stackrel{?}{=} \textbf{PSPACE}\)
  • \(\textbf{L} \stackrel{?}{=} \textbf{P}\)

参考资料

  • Sipser, Introduction to the Theory of Computation, Chapters 7-10
  • Arora & Barak, Computational Complexity: A Modern Approach
  • Garey & Johnson, Computers and Intractability（NP完全性圣经）

相关章节：

评论 #