计算复杂性理论

Calculabilité et Complexité (计算复杂性理论)

概述

本文章是根据法国国立高等电力技术、电子学、计算机、水力学与电信学校 (E.N.S.E.E.I.H.T.) 第八学期课程 “Calculabilité et Complexité” 总结而来的课程笔记。碍于本人学识有限，部分叙述难免存在纰漏，请读者注意甄别。

参考：

• 《计算复杂性理论》- 陈健二教授（广州大学）

---

我们在研究一个问题的复杂度之前，首先需要研究这个问题能否使用计算机解决（可计算性）。

什么是问题？

• 函数问题：给定一个字符串 $\Sigma_*$ 作为输入，经过 $f$ 后输出另一个字符串 $\Sigma_*$

$f: \Sigma_* \to \Sigma_*$

• 决策问题：给定一个字符串 $\Sigma_*$ 作为输入，输出为 $\{_{yes} = 1,\quad _{no} = 0\}$

$f: \Sigma_* \to \{_{yes} = 1,\quad _{no} = 0\}$

实际上可以将字符串集合 $\Sigma_*$ 分成两部分：“yes”的集合和“no”的集合

图灵机

图灵机是一个虚拟的机器，由数学家阿兰·图灵1936年提出来的，尽管这个机器很简单，但它可以模拟计算机的任何算法，无论这个算法有多复杂。

图灵机实际上是解决一个具体问题的程序（算法）

上面是一个图灵机的简单示意图。

• 有限控制器：所谓有限是指该，控制器不随输入的长度变化而变化。对应计算机的CPU
• 无穷的纸带：纸带就像一个计算机的存储器一样。纸带上面的每个格子是空白的，但是可以读写数据
• 读写头：可以向纸带读取或写入数据的指针

可以用如下六元组定义该图灵机

$\mathcal{M} = ⟨Q,\Sigma,\delta,q_s,q_{accept},q_{reject}⟩$

• $Q$ 表示所有状态的集合

• $\Sigma$ 表示字符集，即纸带上只允许出现的字符。例如现代二进制计算机中 $\Sigma = \{0,1\}$

• $\delta$ 是函数，表示该图灵机的每一步该怎么做

  $\delta : Q \times \Sigma \to Q \times \Sigma \times \{L,R,-\}$

  • 输入：当时的状态 $Q$ 、指针所指的字符 $\Sigma$
  • 输出：函数变化后的状态 $Q$ 和字符 $\Sigma$ 、指针运动的方向（L左，R右，-不动）

• $q_s \in Q$，表示初始状态

• $q_{accept} \in Q$，表示停机状态为接受状态，判断为真

• $q_{reject} \in Q$，表示停机状态为拒绝状态，判断为假

【例】

创建一个图灵机以满足

输入：X # Y $: X,Y \in \{二进制数\}$

输出：当 $X = Y$ 时 accept

• $\mathcal{M} = ⟨Q,\Sigma,\delta,q_s,q_{accept},q_{reject}⟩$
• $Q = \{ q_s, q_0, q_1, q_2, q_3, q_4, q_{accept}, q_{reject}\}$
• $\Sigma =$ {0, 1, #, $, _}
• $\delta (Q, \Sigma) = (Q, \Sigma, \{L,R,-\})$

多纸带图灵机

也可以用如下六元组定义该图灵机

$\mathcal{M} = ⟨Q,\Sigma^k,\delta,q_s,q_{accept},q_{reject}⟩$

• $Q$ 表示所有状态的集合

• $\Sigma$ 表示字符集，即每个纸带上只允许出现的字符。

• $\delta$ 是函数，表示该图灵机的每一步该怎么做

  $\delta : Q \times \Sigma^k \to Q \times \Sigma^k \times \{L,R,-\}^k$

• $q_s \in Q$，表示初始状态

• $q_{accept} \in Q$，表示停机状态为接受状态，判断为真

• $q_{reject} \in Q$，表示停机状态为拒绝状态，判断为假

上述的多纸带图灵机可以组合成如下的单纸带图灵机

可以引入符号 $\underline{x}$ 来表示在原来多纸带图灵机中每个指针指向当前字符的位置。

1. 遍历整个纸带。$O(t(n))$
2. 找到符号 $\underline{x}$ 进行操作。$O(t(n)) \times O(t(n))$

Church 公理

Everything we can compute on a physical computer can be comptued on a Turing Machine.

所有的计算模型能做的事情都是一样的，没有任何一个模型能力比图灵机强，只是时间快慢不同。

$图灵机 = 任何计算机上的程序 = 算法$

可计算性理论

根据 Church 公理，我们想要研究一个问题是否是可计算的，我们只需要研究在图灵机上的可计算性。

一个语言 $\mathcal{L}$ 是可以被图灵机所枚举（enumerate）的，如果存在一个图灵机 $\mathcal{M}$，使得输入是 $\mathcal{L}$ 中的串时， $\mathcal{M}$ 输出“接受”；而对非 $\mathcal{L}$ 中的串， $\mathcal{M}$ 输出“拒绝”或不停机。

而一个语言 $\mathcal{L'}$ 是可以被图灵机所决定（decide）的，如果存在一个图灵机 $\mathcal{M'}$，使得输入是 $\mathcal{L}$ 中的串时， $\mathcal{M}$ 输出“接受”；而对非 $\mathcal{L}$ 中的串， $\mathcal{M}$ 输出“拒绝”。注意这里的区别在于，对于图灵机决定的语言，我们需要在所有输出上，该图灵机都要停机。

Definition

An algorithm (or a program or a Turing Machine) $\mathcal{A}$ solves a (desicion) problem $Q$ if on every input $x$, the algorithm $\mathcal{A}(x)$ halts (with an answer yes/no)

一个算法 $\mathcal{A}$ 解决了一个（判断性）问题 $Q$，对于任何一个输入，算法都可以停机（给出一个结果 yes/no）

一个问题 $Q$ 是可解的 (solvable/computable/recursive)当且仅当该问题可以被一个算法 $\mathcal{A}$ 解决。

停机问题 (Halting Problem)

停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。

该问题等价于如下的判定问题：给定一个算法 $\mathcal{A}$ 和输入 $w$，算法 $\mathcal{A}$ 在输入 $w$ 下是否能够最终停止。

该问题不是可解的 (not solvable)，即不存在一个算法 $\mathcal{A}$ 可以判断“另一算法 $\mathcal{A'}$ 是否可以停机”，且算法 $\mathcal{A}$ 也可以停机。

证明1

对角化(Diagonalization)

在上图中，所有的图灵机集合 $\mathcal{TMs}$ 是可数集合（可以列在上图中）；同样的，无穷多的输入集合 $inputs$ 也是可数集合。每个方格意为图灵机 $\mathcal{M}_i$ 在输入为 $x_j$ 的情况下是否可以停机。虽然我们无法确定其是否可以停机，但是否停机一定有一个明确的答案。

我们假设存在一个图灵机 $\mathcal{M}$ 可以判断“另一个图灵机 $\mathcal{M'}$ 在是输入为 $x_i$ 时是否可以停机”，则对于图灵机 $\mathcal{M}$，我们考虑上图中的对角线元素 $\mathcal{M}(\mathcal{M'}_i, \; x_i)$：

⚠️ 请注意区分图灵机 $\mathcal{M}$ 和图灵机 $\mathcal{M’}$ 的区别

• 输入：另一个图灵机 $\mathcal{M'}_i$ 及其输入 $x_i$ ，

• 我们假设一个图灵机 $\mathcal{M}^*$ ：

  if M*(M_i,x_i) == "yes"
  	then dead_looping; // M不停机
  	else return "yes"; // M停机
  halts;
  // 即图灵机M*与M_i的结果相反

因为图灵机 $\mathcal{M}^{*}$ 至少与每一个图灵机 $\mathcal{M}_{i}$ 至少存在一个结果是不同的，

所以图灵机 $\mathcal{M}^{*}$ 不在图灵机集合 $\mathcal{TMs}$ 中，与假设相悖。

证明2

我们仍然假设存在一个图灵机 $\mathcal{M}$ 可以判断“另一个图灵机 $\mathcal{M'}$ 在是输入为 $x$ 时是否可以停机”，则对于图灵机 $\mathcal{M}$：

$\mathcal{M}(\mathcal{M'},x) = \begin{cases} accept \quad \text{if } \mathcal{M'} \text{ halts on } x \\ reject \quad \text{otherwise} \end{cases}$

我们考虑如下自我停机问题：

$\mathcal{M}(\mathcal{M},x)$

后略。

Definition

令 $Q_1$ 和 $Q_2$ 是两个决策性问题，我们说 $Q_1$ 是规约 (reducible) 到 $Q_2$ 的，$Q_1 \le Q_2$，即 $Q_1$ 不比 $Q_2$ 难。如果我们可以找到一个永远可以停机的算法 $\mathcal{A}$ 当输入为 $x$ 时算法输出 $\mathcal{A}(x)$ 是 $Q_1$ 的 “yes”，则 $\mathcal{A}(x)$ 也是 $Q_2$ 的 “yes”。

Lemma

• 如果 $Q_2$ 是可解的，则 $Q_1$ 也是可解的
• 如果 $Q_1$ 是不可解的，则 $Q_2$ 也是不可解的

全接受问题 (Accept-All Problem)

• 输入：图灵机 $\mathcal{M}$
• 问题：图灵机 $\mathcal{M}$ 是否能接受 (accept) 所有 $inputs$ ？

$Q_{Halting} \le Q_{Accpet-All}$

所以全接受问题也是不可解的

等价程序问题 (Program-Equivalence Problem)

• 输入：两个图灵机 $\mathcal{M}_1$ 和 $\mathcal{M}_2$
• 问题： $\mathcal{M}_1$ 和 $\mathcal{M}_2$ 是否做相同的事情 (function)

我们已知停机问题是不可解的，全接受问题也是不可解的。

我们假设一种特殊情况，即图灵机 $\mathcal{M}_0$ 接受所有输入 $inputs$，有：

$Q_{Accpet-All}(\mathcal{M}) \le Q_{Prog-Equ}(\mathcal{M}, \mathcal{M_0})$

• 如果图灵机 $\mathcal{M}$ 处理全接受问题，则 $\mathcal{M}$ 和 $\mathcal{M}_0$ 是等价程序
• 如果图灵机 $\mathcal{M}$ 不是处理全接受问题的，则 $\mathcal{M}$ 和 $\mathcal{M}_0$ 不是等价的

而全接受问题是不可解的，所以等价程序问题也是不可解的。

复杂度理论

推广Church 公理

Everything we can compute in time $t(n)$ (in space $O(s(n))$) on a physical computer can be comptued on a 1-tape Turing Machine in time $t^{O(1)}(n)$ (in space $O(s(n))$).

如果在计算机上做某一件事所花费的时间是 $t(n)$、所占空间是 $O(s(n))$，那么在单纸带图灵机上所花费的时间是多项式时间 $t^{O(1)}(n)$、所占空间是 $O(s(n))$，并不会相差太多。

时空间复杂性

复杂性理论所研究的资源中最常见的是时间（要通过多少步演算才能解决问题）和空间（在解决问题时需要多少内存）。

时间复杂度 $TIME(t(n))$ ：

是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数。时间复杂度越小，说明该算法效率越高，则该算法越有价值。

确定的时间复杂度 $DT_{IME}$

对于一个【确定性】的图灵机，我们可以给出其常见的几种 【(确定的)时间复杂度 $DT_{IME}$】：

• $\mathcal{P}$ 问题类的 (确定的) 时间复杂度 $DT_{IME}$：

Definition

$\mathcal{P} \triangleq \bigcup_{k \in \mathbb{N}} DT_{IME}(n^k)$

即 $\mathcal{P}$ 问题的时间复杂度是【确定性】图灵机的多项式时间复杂度，$\mathcal{P}$ 问题可在多项式时间解决（在很快的时间内解决），$\mathcal{P}$ 问题是易解 (feasible) 问题

• $\mathsf{ETIME}$ 指数时间

$\mathsf{ETIME} \triangleq \bigcup_{k \in \mathbb{N}} DT_{IME}(2^{kn})$

• $\mathsf{EXPTIME}$ 指数时间

$\mathsf{EXPTIME} \triangleq \bigcup_{k \in \mathbb{N}} DT_{IME}(2^{n^k})$

结论

$\mathcal{P} \subsetneq \mathsf{ETIME} \subsetneq \mathsf{EXPTIME}$

• $\mathcal{P}$ 包含在但不等于 $ET_{IME}$ 包含在但不等于 $\mathsf{EXPTIME}$

非确定的时间复杂度 $NT_{IME}$

将在 非确定性 章节讨论。

对于一个决策性问题 $\mathcal{L}$，我们有如下要求：

1. 写一个可以解决问题 $\mathcal{L}$ 的程序
2. 证明这个程序是最优的（目前学界并没有数学上严格的证明）

为了尽量满足要求 2，我们做出了如下妥协措施：

• 我们引入了【规约 (reductions) 】来比较问题的难度
• 我们依照【完整性 (completeness) 】来找出难问题

非确定性 (Non-determinism)

之前我们讲到的图灵机，实际上是在模拟人类的思考方式。

对于一个图灵机 $\mathcal{M} = ⟨Q,\Sigma,\delta,q_s,q_{accept},q_{reject}⟩$，我们在每一个给定的状态下都有唯一一个确定的 $\delta$ 将当前状态转变为下一状态：$\delta (q_0, a_0) = (q_1, a_1, \{L,R,-\})$ 。

但是人类的思考具有不确定性（所谓“突发灵感”），但是图灵机无法模拟这种不确定性行为。

我们希望计算机也有这种特性，即每当计算机面临选择时，我们将不同的选择列出，而让计算机选择一种“最好”的方式执行。

譬如当我们在下棋时，我们经常没办法具体解释落子的原因，我们希望计算机可以选择一种“最好”的方式执行。

回顾 带权图的最短路径问题：

给定一个带权图 $G$，两个顶点 $s$ 和 $t$，以及一个数 $k$，问：我们是否能在图中找到一条路径，使得 $s-t$ 的权值之和 $\le k$？

// 我们假设计算机每次可以找到一条最优路径，其权重为h
v_0 = s;
for (i=1; i<=h; i++)
	// 假设计算机可以"神奇地"找到一个最优的顶点v_i
  for (j=1; j<=h; j++) {ok1 = check [v[i-1], v[i]] is an edge}
  ok2 = check (v_h == t);
  ok3 = check (sum(weight(v[i], v[i+1])) <= k);
  ok =  (ok1 && ok2 && ok3)
  if (ok)
    return 'no'
  	else return 'yes'
// ok, ok1, ok2, ok3 是四个决策性问题，它们很容易解决且是确定的，而不借助"神奇的能力"

那么计算机如何"神奇地"找到一个最优的顶点 $v_i$ 呢？

或用二叉树表示（非确定性图灵机面临的选择不超过两个）：

⚠️注意：这里并不是“计算机遍历所有分支然后选择一条最优路径”而是“我们的计算机有一种特殊的能力，可以直接选择一个最优路径”。

对于一个【确定性】的图灵机：

$\begin{aligned} & \delta (q_0, a_0) = (q_1, a_1, V_1) \\ & \text{(是唯一且确定的)} \end{aligned}$

对于一个【非确定性】的图灵机：

$\begin{aligned} & \delta (q_0, a_0) = (q_1, a_1, V_1) \\ & \delta (q_0, a_0) = (q_2, a_2, V_2)\\ & ... \\ & \delta (q_i, a_i) = (q_i, a_i, V_i), i \in C\\ & \text{(不是唯一且确定的)} \end{aligned}$

Theorem.

在不考虑时间因素的前提下（有效时间*），一个“有神秘能力的”计算机能做的事也可以在一个“没有神秘能力的”计算机上解决。

而在考虑时间因素下（有效时间*），一个“有神秘能力的”计算机能做的事 有时可以 在一个“没有神秘能力的”计算机上解决 (UNKNOWN)。

【*有效时间】是多项式时间，即算法的运行时间是 $O(n^c)$，其中 $c$ 是常数。

非确定的时间复杂度 $NT_{IME}$

• $\mathcal{NP}$ 问题类时间复杂度

$\mathcal{NP} \triangleq \bigcup_{k \in \mathbb{N}} NT_{IME}(n^k)$

即 $\mathcal{NP}$ 问题的时间复杂度是【非确定性】图灵机的多项式时间复杂度。

• $\mathsf{NEXPTIME}$ 指数时间

$\mathsf{NEXPTIME} \triangleq \bigcup_{k \in \mathbb{N}} NT_{IME}(2^{kn})$

结论

• $\mathcal{P} \; \subseteq \; \mathcal{NP} \; \subseteq \; \mathsf{EXPTIME} \; \subseteq \; \mathsf{NEXPTIME}$

• $\mathcal{P} \; \subsetneq \; \mathsf{EXPTIME} \qquad \mathcal{NP} \; \subsetneq \; \mathsf{NEXPTIME}$

• $\mathcal{P} \overset{\underset{\mathrm{?}}{}}{=} \mathcal{NP}$

• $\mathcal{NP} \overset{\underset{\mathrm{?}}{}}{=} \mathsf{EXPTIME}$

• $EXPT_{IME} \overset{\underset{\mathrm{?}}{}}{=} \mathsf{NEXPTIME}$

$\mathcal{P} \overset{\underset{\mathrm{?}}{}}{=} \mathcal{NP}$ 问题

在有效时间下，一个“有神秘能力的”计算机能做的事是否可以在一个“没有神秘能力的”计算机上解决？

等价于

一个（判断性）问题如果在【非确定性图灵机】上有效时间内可解，该问题是否可以在一个【确定性图灵机】上有效时间内可解？

等价于

$\mathcal{P} \overset{\underset{\mathrm{?}}{}}{=} \mathcal{NP}$

• $P$：Polynomial Time 可解
• $NP$：Non-determinism Polynomial

$\mathcal{P}$ 问题与 $\mathcal{NP}$ 问题

• $\mathcal{P}$ 问题类（判断性问题）可在【确定性图灵机】上【多项式时间】内解决（在很快的时间内解决），$\mathcal{P}$ 问题是易解 (feasible) 问题

  the class of (decision) problems that can be solved by polynomial-time [nondeterministic] algorithms(Turing Machines)

• $\mathcal{NP}$ 问题类（判断性问题）可在【非确定性图灵机】上【多项式时间】内解决

  the class of (decision) problems that can be solved by polynomial-time [deterministic] algorithms(Turing Machines)

以下推论都是等价的

• 一个“没有神秘能力的”计算机能做的事可以在一个“有神秘能力的”计算机上解决

• 在【非确定性图灵机】上可以做【确定性图灵机】能做的事

• 【确定性图灵机】不会比【非确定性图灵机】更强

• 所有属于 $\mathcal{P}$ 的问题都是属于 $\mathcal{NP}$ 的

• $\mathcal{P} \subseteq \mathcal{NP} \qquad \text{①}$

反言之，如果：

• 一个“有神秘能力的”计算机能做的事可以在一个“没有神秘能力的”计算机上解决

• 在【确定性图灵机】上可以做【非确定性图灵机】能做的事

• 所有属于 $\mathcal{NP}$ 的问题都是属于 $\mathcal{P}$ 的

• $\mathcal{NP} \subseteq \mathcal{P} \qquad \text{②}$

如果满足以上两点，我们可以推出：

${① + ②} \quad \Rightarrow \quad \mathcal{P} = \mathcal{NP} \quad \text{无人可知是否成立}$

如果 $\mathcal{P} = \mathcal{NP}$ 成立

• 优点：很多工程上很重要的优化问题都可以用计算机解决
• 缺点：所有的密码系统都会被破解

货郎搬运 (Traveling Salesman)问题

在有权图 $G$ 中找到一条路径，每个点只经过一次，要求权值之和为最小 ($\le k$)

1. for(i=1; i<=n; i++)
  // 假设计算机可以"神奇地"找到一个最优的顶点v[i];
2. check that all vertices picked in step1 are different;
3. for(i=1; i<=n-1; i++){
  check [v[i], v[i+1]] is an edge;}
4. check (sum(weight(v[i], v[i+1])) <= k);
5. if (any test in steps 2-4 fails)
  then return ('no')
  else return ('yes')

可满足性 (SAT) 问题

给定一个合取范式 $F$，问 $F$是否可满足 ($F = 1$)？

即找到一组 $X={x_1,x_2,x_3,...,x_n}$ 的取值，使得 $F = 1$。

$\begin{aligned} F = & \quad (\neg x_1 \lor x_2 \lor x_5 \lor \neg x_4)\\ & \land (x_1 \lor x_6 \lor x_5 \lor x_4)\\ & \land (\neg x_5 \lor x_4 \lor \neg x_2)\\ & \land (x_3 \lor \neg x_4)\\ & \land (x_1 \lor \neg x_3 \lor x_6)\\ \end{aligned}$

1. for (each variable x_i in F)
  	// 假设计算机每次都可以"神奇地、正确地"判断出x_i的值是0还是1;
2. if (the assignment constructed in step1 makes F=1)
  	then return ('yes')
    else return ('no')

调度问题 (Scheduling)

我们假设有两个机器 $M_1, M_2$，给定一组 $n$ 个工作，其中完成每个工作需要的时间 $T$ 分别是 $t_1, t_2, t_3, ..., t_n$。我们该如何调度这两台机器，使得完成这 $n$ 个工作所有时间最短？

1. for (each job t_i)
  	// 假设计算机每次都可以"神奇地、正确地"选择出工作t_i可以交给M1或M2机器处理;
2. if (according by step1, both machines M1 and M2 can finish no later than time T)
  	then return ('yes')
		else return ('no')

独立集问题 (Independent Set)

给定一个图 $G$，确定图 $G$ 的独立集中至少包含 $k$ 个顶点。

1. for(i=1; i<=k; i++){
  	// 假设计算机可以"神奇地"找到一个符合的顶点v[i];
		}
2. check (all the vertices picked in step1 are different)
3. check (no two vertices picked in step1 are adjacent 邻接的)
4. if (any check in step2 and step3 fails)
  	then return ('no')
  	else return ('yes')

【转换】SAT 问题 $\Leftrightarrow$ 独立集问题

可满足性 (SAT) 问题

给定一个合取范式 $F$，问 $F$是否可满足 ($F = 1$)？

$\begin{aligned} F = & \quad (\neg x_1 \lor x_2 \lor x_5 \lor \neg x_4)\\ & \land (x_1 \lor x_6 \lor x_5 \lor x_4)\\ & \land (\neg x_5 \lor x_4 \lor \neg x_2)\\ & \land (x_3 \lor \neg x_4)\\ & \land (x_1 \lor \neg x_3 \lor x_6)\\ \end{aligned}$

独立集问题 (Independent Set)

给定一个图 $G$，确定图 $G$ 的独立集中至少包含 $k$ 个顶点。

转换过程

1. 在 SAT 问题中，对于每一个合取的每一个子句（即每一行括号内的元素），我们都可以用一个【完全图】来表示。

2. 不同子句之间的相通元素若互为“非”的关系，则我们将其连接起来。

   例如第一个子句中的 $\neg x_1$ 与第二个子句中的 $x_1$若互为“非”的关系，我们需要将他们连接起来

3. $k = 子句的个数$ 。

4. 如果我们可以在图 $G$ 中找到 $k$ 个相互独立的顶点，则“独立集问题”的结果为【yes】

   等价于

   存在一组 $X={x_1,x_2,x_3,...,x_n}$ 的取值，使得 $F = 1$，即可满足性 (SAT) 问题的结果为【yes】。

5. 至此，我们就将“可满足性 (SAT) 问题”转化成了“独立集问题”

因此，如果一个独立集问题属于 $\mathcal{P}$ 问题类，那么它也是SAT问题。

NP-完全 (complete) 问题

多项式时间规约 (Polynomial-time Reduction)

Definition

我们有两个决策性问题 $Q_1$ 和 $Q_2$，如果存在一个确定性 (det.) 的多项式时间 (poly-time) 算法 $\mathcal{R}$，使得任何一个问题 $Q_1$ 的实例 $x_1$ 都可以转换成问题 $Q_2$ 的实例 $x_2$ ，以至于 $x_1$ 是问题 $Q_1$ 的“yes”实例，当且仅当 $x_2$ 是问题 $Q_2$ 的“yes”实例。那么我们称，

一个决策性问题 $Q_1$ 【多项式时间规约】到另一个决策性问题 $Q_2$，记作 $Q_1 \le^{p}_{m} Q_2$，即 $Q_1$ 不比 $Q_2$ 难，$Q_2$ 不比 $Q_1$ 容易。

$x_1:Q_1的实例 \quad \xrightarrow[poly-time]{\mathcal{R}} \quad x_2:Q_2的实例$

⚠️注意：这里的“实例 $x$”可以理解为关于问题 $Q$ 的一组“解”。

性质

• 如果 $Q_1 \le^{p}_{m} Q_2$，且 $Q_2$ 属于 $\mathcal{P}$ 问题类，那么 $Q_1$ 也属于 $\mathcal{P}$ 问题类。
• 如果 $Q_1 \le^{p}_{m} Q_2$，且 $Q_2$ 不属于 $\mathcal{P}$ 问题类，那么 $Q_1$ 也不属于 $\mathcal{P}$ 问题类。
• 规约具有传递性： $Q_1 \le^{p}_{m} Q_2$， $Q_2 \le^{p}_{m} Q_3$，则 $Q_1 \le^{p}_{m} Q_3$，

$\mathcal{NP}-hard$

对于所有属于 $\mathcal{NP}$ 问题类的问题 $Q'$，如果存在一个问题 $Q$ 满足 $Q' \le^{p}_{m} Q$，那么问题 $Q$ 不比所有的 $\mathcal{NP}$ 问题简单。我们将问题 $Q$ 称作 $\mathcal{NP}-hard$ 问题类。

$\mathcal{NP}-完全\;complete$

如果问题 $Q$ 也属于 $\mathcal{NP}$ 问题类，且满足 $Q' \le^{p}_{m} Q$，那么问题 $Q$ 就是最难的 $\mathcal{NP}$ 问题。我们将问题 $Q$ 称作 $\mathcal{NP}-完全$ 问题类。即满足以下两个条件：

1. 问题 $Q$ 属于 $\mathcal{NP}$ 问题类
2. $所有\mathcal{NP}问题 \le^{p}_{m} Q$，即 $Q$ 是 $\mathcal{NP}-hard$ 问题

推论

• 如果任意一个 $\mathcal{NP}-hard$ 问题都属于 $\mathcal{P}$ 问题，那么 $\mathcal{P} = \mathcal{NP}$
• 如果 $\mathcal{P} \ne \mathcal{NP}$，那么没有一个 $\mathcal{NP}-hard$ 问题可以被【确定的多项式时间算法】解决（学界普遍相信）
• 如果 $Q_1 \le^{p}_{m} Q_2$ 且 $Q_1$ 是 $\mathcal{NP}-hard$ 问题，那么 $Q_2$ 也是 $\mathcal{NP}-hard$ 问题

例，给出一个“天然的” $\mathcal{NP}-完全$ 问题：

Cook Theorem.

SAT (可满足) 问题是 $\mathcal{NP}-完全$ 问题。

证明思路：

1. 证明问题 $Q$ 是 $\mathcal{NP}-hard$ 问题
   • 找到一个已知的 $\mathcal{NP}-完全$ 问题 $Q_1$
   • 证明 $Q_1 \le^{p}_{m} Q$
2. 证明问题 $Q$ 属于 $\mathcal{NP}$ 问题

可满足问题 (SAT)、独立集问题 (Independent Set)、顶点覆盖问题 (Vertex-Cover)、子集求和问题 (Subset Sum)、分区问题 (Partition) 都是 $\mathcal{NP}-完全$ 问题。

空间复杂度 $SPACE(s(n))$ ：

是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是算法优劣的重要度量指标，一般来说，空间复杂度越小，算法越好。我们假设有一个图灵机来解决某一类语言的某一问题，设有 $x$ 个字（word）属于这个问题，把X放入这个图灵机的输入端，这个图灵机为解决此问题所需要的工作带格子数总和称为空间。

确定的空间复杂度 $DS_{PACE}$

类比于时间复杂度，如果存在一台【确定性图灵机】能够在输入为 $x$ 时在 $O(s(n))$ 的空间内判定一个问题 $Q$，那么这个问题属于 $DS_{PACE}(s(n))$ 类。

对于一个【确定性】的图灵机，我们可以给出其常见的几种 【(确定的)空间复杂度 $DS_{PACE}$】：

• $\mathsf{1SPACE}$：指可以在【常数】空间里就可以被【确定性】图灵机解决的决策性问题（例如自增操作）

$\mathsf{1SPACE} \triangleq DS_{PACE}(1)$

• $\mathsf{LSPACE}$：指可以在【对数】空间里就可以被【确定性】图灵机解决的决策性问题（例如比较两数）

$\mathsf{LSPACE} \triangleq DS_{PACE}(\log(n))$

• $\mathsf{PSPACE}$：指可以在【多项式】空间里就可以被【确定性】图灵机解决的决策性问题

$\mathsf{PSPACE} \triangleq \bigcup_{k \in \mathbb{N}} DS_{PACE}(n^k)$

• $\mathsf{EXPSPACE}$：指可以在【指数】空间里就可以被【确定性】图灵机解决的决策性问题

$\mathsf{EXPSPACE} \triangleq \bigcup_{k \in \mathbb{N}} DS_{PACE}(2^{n^k})$

非确定的空间复杂度 $NS_{PACE}$

相同的，如果存在一台【非确定性图灵机】能够在输入为 $x$ 时在 $O(s(n))$ 的空间内判定一个问题 $Q$，那么这个问题属于 $NS_{PACE}(s(n))$ 类。

$NS_{PACE}(s(n)) \subseteq DS_{PACE}(s(n)^2)$

• $\mathsf{NLSPACE}$：指可以在【对数】空间里就可以被【非确定性】图灵机解决的决策性问题（$st-联通度 \text{ CONN}$ 是 $\mathsf{NLSPACE}-\text{complete}$问题 ）

$\mathsf{NLSPACE} \triangleq NS_{PACE}(\log(n))$

• $\mathsf{NPSPACE}$：指可以在【多项式】空间里就可以被【非确定性】图灵机解决的决策性问题

$\mathsf{NPSPACE} \triangleq \bigcup_{k \in \mathbb{N}} NS_{PACE}(n^k) = \mathsf{PSPACE}$

• $\mathsf{NEXPSPACE}$：指可以在【指数】空间里就可以被【非确定性】图灵机解决的决策性问题

$\mathsf{NEXPSPACE} \triangleq \bigcup_{k \in \mathbb{N}} NS_{PACE}(2^{n^k}) = \mathsf{EXPSPACE}$