计算理论：自动机理论

本笔记以经典教材《Introduction to the Theory of Computation, 3rd/4th Edition》为主要线索，仅对最核心的内容进行简要整理。由于我的主要兴趣在人工智能和机器人上，因此这个笔记本整体只整理为一个单页，而非像强化学习、深度学习那样每一章都详细整理为一个单页。

本书以及本课程将带领我们了解这么一个根本性的问题：

计算机的基本能力和局限性是什么？

What are the fundamental capabilities and limitations of computers?

对于一个计算问题，我们很难进行数学分析。因此我们把一个字符串的集合叫做语言，然后把一个问题转化为语言，接着就可以用严格的数学工具来分析问题了。换句话说，任何一个“是/否”形式的计算问题，都可以被看作是一个语言识别问题。

从这个角度来说，计算理论有三个主题，他们其实都是在研究如何使用语言：

1、Automata 自动机（自动机理论）—— Ch.1 - Ch.2

自动机理论研究用什么样的机器可以识别什么样的语言：

最简单的有限自动机能识别什么语言？——正则语言
复杂一点的下推自动机能识别什么语言？——上下文无关语言
最强大的图灵机能识别什么语言？——所有可计算语言

2、Computability 可计算性（可计算性理论）—— Ch.3 - Ch.5

可计算性理论就是研究什么是计算机可以识别的语言（即计算机可以解决的问题），什么事计算机不能识别的语言（即计算机不能解决的问题）。如果我们能找到一个语言，对于这个语言，我们永远无法设计出一个算法（图灵机）来完美判断一个字符串是否属于它，那么这个语言就是不可判定的语言（即计算机不能解决的问题）。比如“停机问题”所对应的语言，就是不可判定的。

3、Complexity 复杂性（计算复杂性理论）—— Ch.6 - Ch.7

计算复杂性理论研究识别一个语言需要耗费多少资源，即探讨在可以解决的问题中，哪些问题容易解决，哪些问题不容易解决。著名的PvsNP问题中，P和NP都是语言的集合。P类语言是那些可以被快速（多项式时间）解决的问题。NP类语言是那些解一旦被猜出，可以被快速验证的问题。P vs NP问题本质上就是在问，这两个语言的集合是否相等。

计算复杂性理论最直接的应用就是密码学，通过找到难计算的问题，来实现安全的加密。

Ch.0 离散数学基础

一般在学习计算理论前要掌握离散数学的基本知识。这里简单过一下离散数学的主要内容，注意这里并不展开讲解离散数学，而是针对计算理论需要的离散数学基础进行简要概述，因此在本部分的案例中也会以计算理论相关的内容为主。

计算理论中最常用的数学工具几乎都来自于离散数学，包括：

Set 集合
Union, Intersection, Complement（并、交、补）
Sequence 序列
Tuple 元组
Cartesian Product 笛卡尔积（Cross Product 叉积）
Function 函数
Mapping 映射
Graph 图
Undirected Graph, Directed Graph （无向图、有向图）
String, Lexicographic Order（字符串，字典序）

Boolean Logic 布尔逻辑：

AND ∧
OR ∨
NOT ¬
Exclusive OR ⊕ （只有1⊕0为0）
Equality ↔
Implication → （只有1→0为0）

定义、定理和证明：

Defination 定义
Mathematical Statement 数学命题
Proof 证明
Theorem 定理
Lemma 引理
Corollary 推论
Counterexample 反例

命题记号：

⟺ iff, if and only if
for P⟺Q:
forward direction: P⟹Q
reverse direction: Q⟹P

证明的类型

Proof by Construction 构造性证明
Proof by Contradiction 反证法
Proof by Induction 归纳法
Basis 归纳基础
Induction Step 归纳步骤

0.1 逻辑与证明方法

归纳法

归纳法（Induction）的证明方法是从小到大逐步推进，先证明base case（比如空串、最短串），再假设长度为k的时候命题成立，然后推出k+1时也成立，整个逻辑链条依赖长度逐步增加的归纳假设。

归纳法非常严谨，适合场景：

语言或者性质与字符串长度紧密相关，比如“任意长度的字符串都满足某种结构”。
要证明递归定义的语言，比如正则表达式生成的语言、递归语法定义的语言。
涉及逐级增长的性质，例如“无论读多少个字符，DFA都保持某个不变性”。

举例：

1758719123259

证明：

This DFA recognizes the language by proof of induction on the length of the input string such that the DFA always ends in the correct state according to the last symbol and the requirement that the string starts with 0.

Base Case:

If w is a single 0, the DFA moves from q₀ to q₁. The DFA does not accept this string because it doesn’t begin with a 0 AND end with a 1.
If w is a single 1, the DFA moves from q₀ to q₃. The DFA does not accept this string and will never accept because it doesn’t begin with a 0.
If w is the empty string, the DFA will immediately reject because it doesn’t begin with a 0 or end with a 1.

Inductive Steps:

Suppose the DFA is in the correct state after reading a string of length k and let w be a string that begins with a 0 and ends with a 1 of length k + 1.

If w began with a 1, the DFA transitioned to q₁ and will never accept due to an infinite loop.
Otherwise, if w began with a 0, the DFA can either be in q₁ or q₂ after reading in k characters.

Now there are two cases:

The last character of w is a 0
The last character of w is a 1

In the first case, if the last character of w is a 0, regardless of whether the DFA is in q₁ or q₂, the DFA will end in q₁ and reject.

In the second case, if the last character of w is a 1, regardless of whether the DFA is in q₁ or q₂, the DFA will end in q₂ and accept.

We know that the DFA only accepts a string iff (if and only if) it ends in q₂ and by the invariant, q₂ means the string starts with 0 and ends with 1.

Conversely, if the string does not begin with 0, the DFA will go into an infinite loop in q₃ and reject.

And if the string does not end with 1, the DFA will end in q₁ and reject.

构造法

构造法（Construction）也叫做分类讨论（Case Analysis），相比于归纳法更为直观易懂，分析方法也比较简单。但是构造法显然无法对涉及任意长度、递归结构的语言进行分类（即无法处理无限分类的情况）。

构造法适合场景：

语言性质比较局部，可以通过有限情况分类来完全覆盖。
DFA的设计明显基于几类不同的模式，直接逐类分析就能得出结论。

举例：

1758719123259

证明：

This DFA recognizes the language by proof of construction by breaking up how the DFA handles strings in different cases.

For any string w, w will either be one of the following:

w begins with a 0 and ends with a 1
w begins with a 0 and doesn’t end with a 1
w doesn’t begin with a 0 and ends with a 1
w doesn’t begin with a 0 and doesn’t end with a 1

In case 1, the DFA must transition to q₁ since w begins with a 0 and it must end up in q₂ because regardless of whether the DFA is in q₁ or q₂ before the last character is read, it will always end in q₂. Therefore, strings in this case will always get accepted.

In case 2, the DFA must transition to q₁ since w begins with a 0 and it must end up in q₁ because regardless of whether the DFA is in q₁ or q₃ before the last character is read, it will always end in q₁. Therefore, strings in this case will always be rejected.

In case 3 and 4 (which can be combined), the DFA must transition to q₃ since w begins with a 1 and will remain in q₃ as the state loops on all inputs. Therefore, strings in this case will always be rejected.

From the above cases, the only strings that can be accepted by this DFA are those that begin with a 0 and end with a 1 (case 1). All other cases result in the string being rejected. Therefore, the DFA recognizes the above language.

反证法

（待补充）

0.2 数学概念和术语

集合、序列和多元组、笛卡尔积

函数、映射、关系

等价关系、偏序关系

单射、满射、双射

可逆性、函数组合

组合数学与计数原理

排列组合
鸽巢原理
基本概率

图论基础

图与子图、树
路径、连通性
欧拉路径、哈密顿路径

数论基础

整除、模运算
素数与同余
对密码学/可计算性有帮助

布尔逻辑（书上0.2.6）

Ch.1 正则语言

1.1 字符串和语言

字符串是计算机科学的重要基础之一。根据应用的要求，可以在各种各样的字母表上定义这样的字符串。按照要求，定义 字母表（alphabet）为任意一个非空有限集合。字母表的成员为该字母表的符号（symbol）。通常用大写希腊字母 $\Sigma$ （Sigma）和 $\Gamma$（Gamma）表示字母表和字母表中符号的打印字符。下面是几个字母表的例子：

\[ \Sigma_1 = \{0,1\} \]

\[ \Sigma_2 = \{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z\} \]

\[ \Gamma = \{0,1,x,y,z\} \]

字符串（string over an alphabet）为该字母表符号的有限序列，通常写为一个符号接着一个符号，不用逗号隔开。设 $\Sigma_1=\{0,1\}$，则 $01001$ 为 $\Sigma_1$ 上的一个字符串。设 $\Sigma_2=\{a,b,c,\cdots,z\}$，则 abracadabra 为 $\Sigma_2$ 上的一个字符串。

设 $w$ 为 $\Sigma$ 上的一个字符串，$w$ 的长度（length）等于它所包含的符号个数，记作 $|w|$。长度为零的字符串叫空串（empty string），记为 $\epsilon$。空串起到的作用像在整数环中的零一样。如果 $w$ 的长度为 $n$，则可写为：

\[ w = w_1 w_2 \cdots w_n, \quad \text{这里每个 } w_i \in \Sigma. \]

它的反转（reverse）是按照相反的顺序写下 $w$ 所得到的字符串，记作 $w^R$，即：

\[ w^R = w_n w_{n-1} \cdots w_1. \]

如果字符串 $x$ 连续地出现在 $w$ 中，则称 $x$ 为 $w$ 的子串（substring）。例如，cad 为 abracadabra 的子串。

设 $x$ 是长度为 $m$ 的字符串，$y$ 是长度为 $n$ 的字符串，$x$ 和 $y$ 的连接（concatenation）是把 $y$ 附加在 $x$ 后面得到的字符串，记为 $xy$，即：

\[ xy = x_1 \cdots x_m y_1 \cdots y_n. \]

可采用上标表示法表示一个字符串自身连接多次，例如 $x^k$ 表示：

\[ \underbrace{xx\cdots x}_{k \text{次}}. \]

字典序（lexicographic order）和大家熟悉的字典顺序一样。通常，我们采用 字符串顺序（shortlex order 或 string order），它在字典序基础上将短的字符串排在长的字符串的前面。例如，字母表 $\{0,1\}$ 上的所有字符串的字符串顺序为：

\[ (\epsilon, 0, 1, 00, 01, 10, 11, 000, \cdots) \]

字符串 $x$ 是字符串 $y$ 的前缀（prefix），如果存在字符串 $z$ 使得 $y = xz$。若且若 $x \neq y$，则 $x$ 称为 $y$ 的 真前缀（proper prefix）。

字符串的集合称为语言（language）。如果语言中任何一个成员都不是其他成员的前缀，那么该语言是 无前缀的（prefix-free）。

1.2 有限状态机

现实中的计算机太复杂，我们从更加简单和抽象的模型开始学习。我们用计算模型（computational model）来抽象一个计算机，只保留我们关心的核心特征。

我们关注状态和状态之间的转换，而不考虑复杂的内存和硬件，因此这种模型叫做有限状态机（finite state machine, FSM），也叫做有穷自动机（finite automaton）。

这里注意，有限自动机只有有限多个状态，没有额外的存储器，因此并非我们今天正在使用的计算机。现在我们用的计算机，更近似于图灵机（严格意义上的图灵机有无限的存储空间，但如今的计算机在存储空间上已经有极大的扩展空间，因此可以认为近似于图灵机），而非有限状态机。

当然，我们的生活中其实有很多有限状态机，比如：红绿灯、自动售货机、遥控器等。

一般情况下，我们主要关注DFA（Deterministic Finite Automaton），即确定性的有限状态机。DFA和NFA的核心区别就是：对于每一个状态，DFA对任何字母表内的合格字符都有着唯一的对应的转移方式；而NFA则不唯一。

一个有限自动机FA可以定义为一个五元组（5-tuple）：

\[ (Q, \Sigma, \delta, q_{0}, F) \]

where

$Q$ is a finite set called the states 状态集合
$\Sigma$ is a finite set called the alphabet 字母表
$\delta : Q \times \Sigma \to Q$ is the transition function 转移函数
$q_{0} \in Q$ is the start state 起始状态
$F \subseteq Q$ is the set of accept states 接受状态集

其中，FA必须有start state，但是特殊情况中accept states可以为空。

上述五元组也叫做有限自动机（Finite Automaton, FA）的形式化定义。 这个五元组之所以是“形式化”的，是因为它使用了精确的数学语言（集合、函数等）来描述一个自动机，没有任何模糊不清的地方。它精确定义了：

有哪些状态 (Q)
能接收哪些输入符号 (Σ)
如何从一个状态转移到另一个状态 (δ)
从哪个状态开始 (q0)
哪些状态是最终的成功状态 (F)

任何一个有限自动机，无论它多么复杂，都可以用这样一个五元组来毫无歧义地描述。这就是“形式化定义”的核心。

我们在绘制DFA的时候，用一个没有来源的箭头指向start state，然后用两个圈来代表accept state；accept state不一定存在，也不一定只有一个。下图是一个状态转移图的例子：

1758724039765

如果A是机器M可以接受的一串string，那么我们就说：A is the language of machine M, 并写作：

\[ L(M) = A \]

We say that M recognizes A, or M accepts A. 一台FA机器可以接受若干字符串，但它永远只能识别一个语言。

我们可以用简明的描述（Concise Description）来描述一个DFA：

集合形式
正则表达式
语言表达

1758724348162

以上图为例，可以用语言表述：

M2 accepts exactly the set of binary strings that end with a 1.

也可以用集合形式表述：

\[ L(M_2) = \{ w \mid w \text{ ends in a } 1 \} \]

或者用正则表达式：

\[ L(M_2) = (0 + 1) * 1 \]

上面三种都是concise description。

例1： 识别状态转移图，描述该DFA的语言：

1758724847567

我们可以绘制一个状态表，或者代入查看转移关系。可以发现，当接收0时，状态转移到q1；否则转移到q2。q1是accept state。也就是说，该DFA或者说Machine接收的是以0为结尾的字符串。即：

\[ L(M) = \{\, w \mid w \text{ is the empty string } \varepsilon \text{ or ends in a } 0 \,\}. \]

例2： 识别下列DFA所示语言

1758725025103

这个图中你会发现一旦接收到状态，要么去q1，要么去r1，没有返回s的情况。所以这个Machine记住了第一个符号。即如果最后接收的是a，那么第一个字符就是a；如果最后接收的是b，那么第一个字符就是b。更进一步地，该Machine接收开始与结束符号相同的字符串。即：

\[ L(M) = \{\, w \mid w \text{ starts and ends with the same symbol} \,\} \]

例3： 识别下列DFA所示语言

1758725231656

这个Machinbe多了一个 <RESET>，这个是特殊符号。上述DFA从q0开始，如果是0就接受，1的话到q1，2的话到q2；在q1这里如果是2就返回q0然后被接受；在q2的话如果是1就回到q0……仔细观察，会发现这就是一个模运算FA。RESET的作用是暂停当前的模运算，进行新的模运算。

我们可以把这个DFA进行泛化，对任意数字进行取模运算，可得如下Machine：

For each $i \geq 1$ let $A_i$ be the language of all strings where the sum of the numbers is a multiple of $i$, except that the sum is reset to $0$ whenever the symbol $\langle \text{RESET} \rangle$ appears.

For each $A_i$ we give a finite automaton $B_i$, recognizing $A_i$. We describe the machine $B_i$ formally as follows:

\[ B_i = (Q_i, \Sigma, \delta_i, q_0, \{ q_0 \}), \]

where $Q_i$ is the set of $i$ states $\{ q_0, q_1, q_2, \dots, q_{i-1} \}$, and we design the transition function $\delta_i$ so that for each $j$, if $B_i$ is in $q_j$, the running sum is $j \pmod{i}$.

For each $q_j$ let:

\[ \begin{aligned} \delta_i(q_j, 0) &= q_j, \\ \delta_i(q_j, 1) &= q_k, \quad \text{where } k = j+1 \pmod{i}, \\ \delta_i(q_j, 2) &= q_k, \quad \text{where } k = j+2 \pmod{i}, \\ \delta_i(q_j, \langle \text{RESET} \rangle) &= q_0. \end{aligned} \]

例4： 设计一个DFA，识别“至少包含一次字串001的二进制string”

解题思路:

忽略所有的1
一旦看到0，就记住可能是001的第一个0
接着如果还是0，就记住可能是001的00
接下来如果又是一个0，则仍然保持00状态
在00状态下看到1，则找到了解，accept

1758725603425

1.3 形式化定义

在上一节我们了解了五元组形式化定义（formal definition）和简明描述方法（concise description）。上面我们提到，在计算理论中，一个字符串的集合叫做“语言”（Language），这个集合可以包括有限或无限个字符串。

注意区分字母表和语言：

字母表（Alphabet）是有限的字符集合
语言（Language）是字符串的集合，是字母表中字符的有限序列

比如：

\[ L_{1} = \{\, \text{"cat"}, \text{"dog"}, \text{"fish"} \,\} \quad (\text{有限集合}) \]

\[ L_{2} = \{\, \text{所有以 "ab" 结尾的字符串} \,\} \quad (\text{无限集合，如 "ab", "aab", "bab", }\dots) \]

当一个自动机M能够对每一个传递给它的字符串w，给出一个“接受”（Accept）或者“拒绝”（Reject）的结论的时候，那么我们说：

\[ A = \{\, w \mid M \ \text{accepts } w \,\}. \]

上述描述有两层含义：

M接受的字符串，都在语言A里
M拒绝的字符串，都不在语言A里

因而，自动机M是语言A的一个完美的、精确的“定义”，或者说“规则”。如果一个语言能够找到一个对应的按照上述方式进行描述的FA，这个FA能够用上述的方式识别这个语言，那么我们就说这个语言是一个正则语言（regular language）。同理，如果一个语言不能找到这样的对应的FA，那么这个语言就不是正则语言。

例如：

所有以1结尾的binary string: FA只需要判断最后一个字符是不是1，因此是正则语言。
所有包含007的string：可以设计几个状态来追踪是否有连续的007，因此是正则语言。
所有由n个0后面跟着n个1组成的字符串：因为FA没有记忆能力，因此你无法设计出一个FA来设别这个语言，因此这个并非正则语言。

1.4 正则运算

闭包性质

闭包（Closure） 是一个数学概念，描述的是集合和运算之间的关系。其主要内容是：如果一个集合里的成员，在经过某种运算后产生的结果依然在这个集合内，那么这个集合就是封闭的（Closed）。

比如说：

对于所有整数，加法运算是封闭的。
对于所有证书，除法运算不是封闭的，因为整数除以整数可能是小数。
对于所有奇数，加法运算是不封闭的。（奇数+奇数=偶数）
字符串在拼接（concatenation）运算下是封闭的。
布尔值集合在AND运算下是封闭的。

闭包性质是一个检验工具，用来描述一个集合在某种运算下是否自给自足。在计算理论中，“正则语言在正则运算下具有闭包性” 是一个核心定理。这个定理是构建正则表达式、编译器等高级工具的理论基石。

并运算 Union

以及并运算的闭包性质

假设A和B是两个语言，则并运算：

\[ A \cup B = \{ x \mid x \in A \;\text{or}\; x \in B \} \]

连接运算 Concatenation

以及连接运算的证明闭包性质

假设A和B是两个语言，则连接运算：

\[ A \circ B = \{ xy \mid x \in A \;\text{and}\; y \in B \} \]

星号运算 Star

以及星号运算的证明闭包性质

假设A和B是两个语言，则星号运算：

\[ A^* = \{ x_1 x_2 \cdots x_k \mid k \geq 0 \;\text{and each } x_i \in A \} \]

1.5 正则表达式

一个使用代表‘并、连接、星号’的符号，把代表最基础语言（如 {a}、{ε}）的符号，组合起来的式子，就是正则表达式。我们之前提到，能用FA识别的语言就是正则语言。在学习正则运算符号后，我们现在又获得了一个新的判定方法：能用正则表达式表达的语言，就是正则语言。

就描述能力而言，正则表达式和DFA是等价的。换句话说，所有的DFA都可以用正则表达式来描述。任何一个DFA（确定性有限自动机）所能识别的语言，都一定可以用一个正则表达式来描述。反之，任何一个正则表达式所描述的语言，也一定可以用一个DFA来识别。

这不仅仅是一个巧合，而是由一条著名的定理——克林定理 (Kleene's Theorem) 所保证的。这个定理揭示了一个深刻的等价关系：

正则表达式 (Regular Expressions) ⇔ 有限自动机 (Finite Automata)

具体来说，下面这三种描述语言的方式，它们在表达能力上是完全等价的：

正则表达式 (Regular Expression)
非确定性有限自动机 (NFA)
确定性有限自动机 (DFA)

它们都能且仅能描述同一类语言，这类语言被称为 “正则语言” (Regular Languages) 。

这种等价关系意味着我们有明确的算法可以在这几种形式之间进行转换：

正则表达式 → NFA ：我们可以用一种叫做“汤普森构造法” (Thompson's construction) 的算法，将任意一个正则表达式转换成一个等价的NFA。
NFA → DFA ：我们可以用“子集构造法” (Subset construction) 将任意一个NFA转换成一个等价的DFA。
DFA → 正则表达式 ：同样，我们也有算法（例如“状态消除法” State Elimination Method 或 Brzozowski's Algebraic Method）可以将任意一个DFA转换成一个等价的正则表达式。

总结一下上面的几节内容，其实就是：

首先我们了解什么是正则语言：能被FA识别的就是正则语言。
然后我们学习三个正则运算符号：并、连接、星号。
接着我们了解到，正则运算符合闭包性质。
最后我们升华到：能用正则运算表达的就是正则语言。

在Ch1.正则语言中，我们了解到以下内容相互等价：

有穷自动机 Finite Automata: DFA/NFA
正则表达式 Regular Expressions
正则文法 Regular Grammar
五元组 5-Tuple

正则语言封闭于以下主要运算：

并集 (Union): $L_{1} \cup L_{2}$
连接 (Concatenation): $L_{1} \cdot L_{2}$
克莱尼星号 (Kleene\ Star): $L_{1}^{*}$
交集 (Intersection): $L_{1} \cap L_{2}$
补集 (Complement): \overline{$L_{1}$}
差集 (Difference): $L_{1} - L_{2}$

正则语言位于乔姆斯基谱系 (Chomsky Hierarchy)这个形式语言谱系的 最底层 (Type-3) ，是能力最弱但也是最容易分析的一类：

Type-0：递归可枚举语言 (Turing Machines)
Type-1：上下文相关语言 (Linear-Bounded Automata)
Type-2：上下文无关语言 (Pushdown Automata)
Type-3：正则语言 (Finite Automata)

因此，学完正则语言后，我们就要继续学习上下文无关语言和图灵机。从隶属关系（完整的语言集合包含关系）和对应的机器能力关系上来说：

正则语言 ⊂ 上下文无关语言 ⊂ 上下文相关语言 ⊂ 图灵机可判定的语言
有限自动机 < 下推自动机 < 线性有界自动机 < 图灵机

1.6 泵引理

如果我们现在遇到了一个语言L，我们想知道这个语言是什么，我们可以通过如下思路来分析：

首先，我们尝试为该语言构造一个DFA/NFA/正则表达式，如果构造成功，那么语言L就是正则语言
如果构造失败，那么我们怀疑L可能不是正则语言，那么我们就用正则语言的泵引理来证明该语言不满足泵送条件。如果证明成功，那么这个语言就不是正则语言。
如果这个语言不是正则语言，那么我们就尝试为改语言构造一个下推自动机PDA或者上下文无关文法CFG。如果构造成功，那么就证明L是上下文无关语言CFL。
如果构造失败，那么我们怀疑该语言不是CFL，那么我们就要用上下文无关语言的泵引理。如果证明成功，那么这个语言就不是上下文无关语言。
如果这个语言不是上下文无关语言，那么我们可以继续判断他是否是上下文相关语言或者递归可枚举语言；如果能成功构造线性有界自动机LBA或者图灵机Turing Machine，那么他就是上下文相关语言或者递归可枚举语言。

在正则语言和上下文无关语言的阶段，泵引理是最好用的工具；但是到了上下文相关语言和图灵机的阶段，泵引理便不再好用了。所以我们在这里主要讨论正则语言的泵引理和上下文无关语言的泵引理。

正则语言的泵引理（Pumping Lemma）可以用来证明一个语言不是正则语言。 换句话说，正则语言的泵引理（本章中简称泵引理）是一个证伪工具，我们可以通过假设语言L是正则，然后发现L不满足泵引理性质，来推论一个语言不是正则；但是如果一个语言L满足泵引理的性质，我们不能断定他就是正则语言。

考虑语言：

\[ B = \{0^n1^n \mid n \geq 0\} \]

\[ C = \{\,w \mid w \text{ 中 }0\text{ 和 }1\text{ 的数量相等}\,\} \]

\[ D = \{\,w \mid w \text{ 中出现子串 }01\text{ 和 }10\text{ 的次数相等}\,\} \]

上面的语言中，0和1出现的次数都可能是无限个，但是我们很难直观地判断哪一个不是正则语言、哪一个是正则语言。因为上面的三个语言中：B和C不是正则语言，但D是正则语言。

因此，我们需要一个好用的、严格的方法，来判断一个语言是否是正则的。

我们一般用泵引理来证明语言的非正则性。为什么叫“pumping lemma”呢？ “pump”的意思就是打气，你可以想象给一个自行车打气：你不停地把打气筒按下去又拉上来、按下去又来上来，这个动作非常地重复且有规律。

比如说，我们现在有一个字符串“xyyyyyyz”，那么显然中间的y可以通过pump的方式打进去，于是这个字符串就可以改写成“x{pump:y}z”。

现在来看Pumping Lemma: If A is a regular language, then there is a number $p > 0$ (the pumping length) where if $s$ is any string in A of length at least $p$, then $s$ may be divided into three pieces, $s = xyz$, satisfying the following conditions:

for each $i \geq 0, xy^{i}z \in A$，这里的$y^i$代表连续i个y连接在一起
$\lvert y \rvert > 0$，这里的双竖线包围代表字符串y的长度
$\lvert xy \rvert \leq p$

$y$的长度不为0也记作$y \ne \varepsilon$，这个记法在形式语言、分析学、自动机理论中特别指代空字符串（katex格式为\varepsilon）。当字符串s被划分为xyz的时候，x或z可以使空字符串，但y不能是空字符串。这个条件是pumping lemma的灵魂。condition 3的规定的含义是：可以被pumping的部分必须出现在字符串的开头，也就是前p个字符内。

总之，记住下面这几个关键信息：

pumping length p > 0
exist string s, |s| >= p
$xy^{i}z \in A$
|xy|<=p
|y|>0

解题步骤就是：

从pumping lemma获得p
选择一个s，满足|s|>=p且s属于L
列举pumping lemma的三个性质
把s拆分开看，发现xy的内容
pumping y，得到s'
发现s'不属于L，反证结束

现在我们回头看刚才的B、C、D这三个语言。

EXAMPLE 1

$B = \{0^n1^n \mid n \geq 0\}$

首先我们假设B是正则语言，那么B一定符合泵引理。设p>0为泵长度，那么必然有一个字符串s，有|s|>=p，属于B。根据泵引理，我们有：s=xyz, s'=xy^iz也属于B，且|xy|<=p, |y|>0.

现在，我们选择n=p, 那么s=xyz。由于|xy|<=p, 所以xy只包含0，那么y也只包含0。现在，根据泵引理，我们假设i=2，那么s'=xyyz也属于B。由于y中只包含0，所以s'相比于s只增加了y的数量，且增加了至少一个0。而由于z的数量没有变，因为1只存在于z中，所以s'中1的数量没有变。

我们发现，xyyz由于0和1的数量不相等，所以xyyz不属于B。这与我们的假设相悖，因此B不是正则语言。

EXAMPLE 2

$C = \{\, w \mid w \text{ has an equal number of }0\text{s and }1\text{s} \,\}$.

这个可以直接用B的反例来证明，因为C是B的一个特例，所以B中那个反例在C这里也适用。

EXAMPLE 3

\[ F = \{\, ww \mid w \in \{0,1\}^* \,\} \]

这个和上面的还是很像，可以把B中的情况double一下，组成一个特例，然后反证。

令$s=0^p1^p0^p1^p$，则|s|=4p>=p。拆分s为xyz, 由于|xy|0，所以y只有0。接着pumping，让i=2，然后s'=xyyz，则新字符串中的0增加了，这导致$0^{p+增加}1^p$和后半部分的$0^p1^p$的长度不再相等，从而导致s'不属于F，与假设相悖，因而证明了F不是正则语言。

EXAMPLE 4

$D = \{\, 1^{n^{2}} \mid n \geq 0 \,\}$

这个语言的意思是该语言仅由1组成，其长度由指数$n^2$决定。

证明方法：令n=p, 把s拆分为s=xyz, 令i=2，那么$s'=xyyz, |s'|=|s|+|y|=p^2+k$，那么我们的任务其实就变成了证明$p^2+k$不是平方数。由于p是整数，所以$p^2$的下一个数是$(p+1)^2$，即$p^2+2p+1$，由于$1 \leq \lvert y \rvert \leq p$，所以$p^2 < p^2 + k \leq p^2+p < p^2 + 2p + 1$，因此pumping后长度达不到下一个平方数，也就是说pumping后的s'的长度不是一个平方数，从而证明D不是正则语言。

EXAMPLE 5

证明一个语言不是回文。

这种类型可以通过闭包性质：如果L不是回文同时是正则语言，那么他的补集也是正则语言。接着我们只需要证明L的补集（回文语言）不是正则语言就行了。

Ch.2 上下文无关文法

2.1 CFG与CFL

在第一章节的末尾，我们学习了如何使用泵引理来证明一个语言不是正则语言，比如经典的例子：

\[ \{0^n1^n \mid n \ge 0\} \]

由于0和1的数量都是无限且不确定数量的，我们没有办法构造出一个DFA来描述这个语言。本章我们来学习一个可以描述上述语言的上下文无关文法（Context-Free Grammar, CFG），在乔姆斯基谱系 (Chomsky Hierarchy) 这个形式语言谱系的 第二层 (Type-2) ，是能力最弱但也是最容易分析的一类：

Type-0：递归可枚举语言 (Turing Machines)
Type-1：上下文相关语言 (Linear-Bounded Automata)
Type-2：上下文无关语言 (Pushdown Automata)
Type-3：正则语言 (Finite Automata)

上下文无关文法CFG在程序设计语言中有着重要的应用。当设计人员编写程序设计语言的编译器和解释器时，常需先获取该语言的文法。因此，大多数编译器（Compiler）和解释器都包含一个语法分析器（parser），它在生成编译代码或解释程序执行前，提取出程序的语义。

与上下文无关文法相关的语言集合称为上下文无关语言（Context-Free Language, CFL）。请注意，上下文无关语言是包含正则语言的。

上下文无关文法由一组替换规则（substitution rule）组成，替换规则又称为产生式（production）。每条规则占一行，由一个符号和一个字符串构成。

例如文法$G_1$：

\[ \begin{aligned} A &\rightarrow 0A1 \\ A &\rightarrow B \\ B &\rightarrow \# \end{aligned} \]

上面的三行指令就是替换规则（Substitution Rule）或者说产生式（Productions）。它的含义是：

一个A可以变成一个0、一个A和一个1的组合
一个A也可以变成一个B
一个B可以变成一个#

其中可以被替换的符号，叫做Variables（变量）或Non-terminals（非终结符），在上面A和B可以被替换，因此A和B就是变量。

其中不能再被替换的符号，叫做终结符（Terminals）。这些不能被替换的符号，就是我们造句过程中的基础积木，是最终成品的组成部分。在上面的文法中，终结符有0、1、#。

起始变量（Start Variable） 是造句的起点，一般按照惯例，它就是第一条规则左边的那个变量，在上面的文法中就是A。

那我们如何用这个文法造句呢？我们从起始变量A出发，不断应用规则替换，最终得到一个只包含终结符的字符串，就完成了造句。比如：

从A起始，目标是造一个句子00#11
A
0A1
0(0A1)1
00B11
00#11，推导完毕

上面这个过程叫做派生（derivation）。凡是能通过上述推导过程造出来的句子，都符合这个文法，叫做文法的语言（language of the grammar）。能够用上下文无关文法生成的语言称为上下文无关语言（CFL）。

上面的文法例子的特点是，#号两边的0和1的数量必须相等。如果我们把它写为语言，那么这个语言就是：

\[ \{0^n\#1^n \mid n \ge 0\} \]

任何不满足上面规律的字符串，都是这个文法造不出来的，比如：

00#1
01#
0011
a#b

为了方便，我们把可以派生出多种结果的变量写作：

\[ \begin{aligned} A &\rightarrow 0A1 | B\\ B &\rightarrow \# \end{aligned} \]

2.2 形式化定义

上下文无关文法的形式化定义是一个4-tuples：

Set of Variables: $V$
Set of Terminals: $\Sigma$
Set of Rules: $R$
Start Variable: $S$

例如：

\[ \begin{aligned} &\text{Set of Variables (V): } V = \{P\} \\ &\text{Set of Terminals } (\Sigma): \Sigma = \{a, b, (, ), \cup, *, \emptyset\} \\ &\text{Set of Rules (R):} \\ &P \rightarrow a \\ &P \rightarrow b \\ &P \rightarrow \emptyset \\ &P \rightarrow (P) \\ &P \rightarrow P \cup P \\ &P \rightarrow PP \\ &P \rightarrow P* \\ &\text{Start Variable (S): } S = P \end{aligned} \]

2.3 下推自动机

待复习：下推自动机PDA等

2.4 泵引理

待复习：上下文无关语言的泵引理

2.4 DCFL

待复习：确定型上下文无关语言

2.5 封闭性

参考作业3的第一题。

Ch.3 图灵机

3.1 图灵机

3.2 形式化定义

一个图灵机由一个7-tuples组成，以二进制数加一的图灵机为例：

Set of States (Q):

$$ Q = {Start, Carry, Back, End} $$ 2. Input Alphabet (Σ):

$$ \Sigma = {0, 1} $$ 3. Tape Alphabet (Γ):

$$ \Gamma = {0, 1, -} $$ 4. Transition Function (δ):

$$ \begin{aligned} \delta(Start, 0) &= (Start, 0, R) \ \delta(Start, 1) &= (Start, 1, R) \ \delta(Start, -) &= (Carry, -, L) \[6pt] \delta(Carry, 1) &= (Carry, 0, L) \ \delta(Carry, 0) &= (Back, 1, L) \ \delta(Carry, -) &= (Back, 1, L) \[6pt] \delta(Back, 0) &= (Back, 0, L) \ \delta(Back, 1) &= (Back, 1, L) \ \delta(Back, -) &= (End, -, R) \end{aligned} $$ 5. Start State:

$$ q_0 = Start $$ 6. Accept State:

$$ q_{\text{accept}} = End $$ 7. Reject State:

$$ q_{\text{reject}} = \emptyset $$

3.3 丘奇-图灵论题

1900年，数学家希尔伯特在巴黎举行的世界数学家大会上提出了23个数学问题，其中第十个是关于不定方程的可解答性的，也就是给定一个不定方程：

\[ a_1 x_1^{b_1} + a_2 x_2^{b_2} + \cdots + a_n x_n^{b_n} = c \]

希尔伯特的问题是：能否给定一个这样的任意多个未知数的不定方程（丢番图方程），通过一种可行的方法（希尔伯特所说的verfahren，就是我们今天所说的algorithm），经过有限次运算，可以判定该方程是否有整数解。

虽然早在古希腊以及春秋时代，人们就知道可以使用类似辗转相除法这样的方式进行运算。但是，到了希尔伯特的时代，人们依然对于什么是可行的计算，仍然没有精确的概念。一个问题可解与不可解，究竟是什么含义，当时的人们还不得而知。

1936年，丘奇（Alnozo Church）和图灵（Alan Turing）给出了该问题的定义。丘奇使用称为$\lambda$演算的记号系统来定义算法，而图灵则使用机器来做同样的事情。这两个定义后来被证明是等价的，因而算法的非形式化概念和精确定义之间的这个联系从此被称为丘其-图灵论题（Church-Turing Thesis）：

Intuitive notion of algorithms

EQUALS

Turing machine algorithms

即：算法的直观概念等于图灵机算法。简单来说，丘奇-图灵论题断言：任何我们直观上认为可计算的问题，或者说任何存在算法能解决的问题，都等价于可以用一台图灵机来解决。

丘奇-图灵论题提出的算法定义是解决希尔伯特第10问所必需的。1970年，马提亚塞维奇证明了该问题。

Ch.4 可判定性

1761016039627

4.1 可识别的语言

详见下一节。

4.2 可判定的语言

我们说图灵机 $M$接受$w$，是指机器从一个起始配置 $C_1$ (即机器在初始状态 $q_0$，磁带上写着 $w$，读写头在 $w$ 的开头) 开始运行。经过一系列的单步状态转移 ( $C_i$ 产生 $C_{i+1}$ )，机器最终达到了一个“接受配置” $C_k$ (即机器的状态变成了 $q_{\text{accept}}$)。只要存在这样一条能达到 $q_{\text{accept}}$ 的路径，我们就说 $M$ 接受 $w$。

基于“接受”的定义，我们就可以定义一个图灵机的“语言”：

定义：一个图灵机 $M$ 的语言，记作 $L(M)$，是所有 $M$ 能够接受的字符串 $w$ 的集合。
数学表示 ：$L(M) = \{w \mid M \text{ accepts } w\}$

现在，基于 $L(M)$ 的概念，我们来定义两种不同“难度”的语言：

(A) 图灵可识别语言 (Turing-recognizable)

定义：一个语言 $L$ 是 图灵可识别的 ，如果存在一个图灵机 $M$，使得 $L(M) = L$。
通俗讲解 ：
如果一个字符串 $w$ 在这个语言 $L$ 中 (即 $w \in L$)，那么这个图灵机 $M$ 运行后一定会停机并接受 (accept) $w$。
如果一个字符串 $w$ 不在这个语言 $L$ 中 (即 $w \notin L$)，那么 $M$ 运行后有两种可能：
1. 停机并拒绝 (reject)。
2. 永不停机 (陷入无限循环)。
核心点 ：这种机器只需要对“是”的答案（$w \in L$）给出肯定的答复（停机并接受）。它不需要保证对“否”的答案一定能停机。

(B) 图灵可判定语言 (Turing-decidable)

定义：一个语言 $L$ 是 图灵可判定的 ，如果存在一个“判定器” (Decider) $M$ 来决定它。
什么是“判定器” (Decider)？
“判定器”是一种特殊的图灵机，它保证对任何输入都永远不会进入无限循环。它总会在有限的时间内停机，并给出“接受”或“拒绝”的答案。
通俗讲解 ：
如果一个字符串 $w$ 在这个语言 $L$ 中 (即 $w \in L$)，判定器 $M$ 会在有限时间内停机并接受 (accept)。
如果一个字符串 $w$ 不在这个语言 $L$ 中 (即 $w \notin L$)，判定器 $M$ 也会在有限时间内停机并拒绝 (reject)。
核心点 ：这种机器（判定器）必须对所有输入（无论是“是”还是“否”）都能在有限时间内停机并给出明确的答案。

特性	图灵可识别 (Turing-recognizable)	图灵可判定 (Turing-decidable)
对于$w \in L$(在语言中)	必须停机并接受	必须停机并接受
对于$w \notin L$(不在语言中)	可以停机并拒绝，也可以永不停机	必须停机并拒绝
是否总停机？	不一定	是，总会停机

总结来说，Decider 判定器必须保证停下来，即无论你给他什么问题（输入），他都必须在有限的时间内完成计算，然后亮起一盏灯：

Accept，接受，代表是
Reject，拒绝，代表否

Decider总会停机（Halts on all inputs），绝对不会陷入死循环或者无限思考中。如果一个问题能被Decider回答，那么这个问题就是Decidable（可判定的）。

如果一个语言 L 和它的补集都是可识别的，那么 L 就是 可判定（decidable） 的。（因为可以并行运行两个识别器，一个认L，一个认L的补集，必有一个会停）。

定理：一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。换句话说，一个语言是可判定的，当且仅当他和他的补都是图灵可识别的。

例1： “这个数字 $N$ 是不是偶数？”

判定器工作：

接收数字 $N$。
计算 $N$ 除以 2 的余数。
如果余数是 0，停机并回答 “是” 。
如果余数是 1，停机并回答 “否” 。

分析： 这个过程非常快，而且对于任何数字 $N$，它都保证会停下来给出一个明确的“是”或“否”的答案。所以，这是一个 Decider。

例2：令 $M$ 为一个图灵机，$w$ 为 $M$ 的输入字母表中的一个字符串。考虑以下问题：

$A = \{\langle M, w \rangle \mid M \text{ 在 } w \text{ 上的计算中在某个点向左移动}\}$

证明 $A$ 是可判定的（decidable）。

解答：

要证明一个语言是可判定的，我们必须构造一个“判定器” (Decider)。这个判定器是一个图灵机，它在任何输入上都必须停机 (always halts)，并给出正确的“接受”或“拒绝”的答案。

这个问题的核心难点在于：我们如何处理 $M$ 在 $w$ 上无限循环的情况？

我们要构造一个判定器 $D$ (Decider)，它来判定语言 $A$： $A = \{\langle M, w \rangle \mid M \text{ 在 } w \text{ 上的计算中至少移动过一次左 (Left)}\}$

我们将构造一个判定器 $D$。$D$ 会模拟$M$ 在 $w$ 上的运行，但它会 设置一个最大步数限制 ，以防止 $M$ 无限循环导致 $D$ 自己也无限循环。

关键在于证明：如果 $M$ 永远不向左移动，它要么在有限步数内停机，要么会进入一个可被检测到的无限循环。

判定器 $D$ 在收到输入 $\langle M, w \rangle$ 后，执行以下操作：

1、获取 $M$ 和 $w$ 的参数 ：

令 $k$ 为 $M$ 的状态数量 ($|Q|$)。
令 $g$ 为 $M$ 的带字母表大小 ($|\Gamma|$)。
令 $n$ 为 $w$ 的长度 ($|w|$)。（如果 $w$ 是空串， $n=1$）。

2、计算一个“最大步数”界限 (Bound) ：

界限 1 (在输入 $w$ 上循环)： 如果 $M$ 的读写头始终保持在 $w$ 的 $n$ 个格子内（即位置 1 到 $n$）并且从不向左移动（即只移动 'R' 或 'S'），那么它的“配置”(configuration) 可以由 (当前状态, 读写头位置, $n$ 个格子的内容) 来定义。

可能的状态数：$k$
可能的读写头位置：$n$
可能的带内容：$g^n$
总的配置数 $B_1 = k \times n \times g^n$。
如果 $M$ 在 $w$ 上运行超过 $B_1$ 步并且读写头从未超过第 $n$ 个格子，它一定重复了某个配置，因此它陷入了一个永不向左的无限循环。

界限 2 (在空白带上循环)： 一旦 $M$ 的读写头移动到 $w$ 之后的空白带上（即位置 $> n$）并且从不向左移动，它就永远不会再回头读取 $w$。

此时，它的行为只取决于它的（当前状态）和它（当前读取的带符号）。
可能的（状态, 符号）组合数：$B_2 = k \times g$。
如果 $M$ 在空白带上运行超过 $B_2$ 步（并且从未向左移动或停机），它一定重复了某个（状态, 符号）组合。因为它右边的带总是相同的（全是 $\sqcup$ 或它自己写下的符号序列），它将陷入一个永不向左的无限循环。

总界限 ：我们设置一个总的模拟步数 $B = B_1 + B_2$。

3、开始有限模拟 ：

模拟 $M$ 在 $w$ 上的运行，但最多只模拟 $B$ 步。
在模拟的每一步中 ：
情况 (a) ：如果 $M$ 的转移函数指示它 向左移动 (L) ，则 $D$ 停机并接受 (ACCEPT) 。（因为 $\langle M, w \rangle \in A$）
情况 (b) ：如果 $M$ 停机（进入 $q_{\text{accept}}$ 或 $q_{\text{reject}}$），则 $D$ 停机并拒绝 (REJECT) 。（因为它停机了却从未向左移动）
情况 (c) ：如果模拟 达到了 $B$ 步，而 $M$ 既没有向左移动，也没有停机。

4、得出结论 ：

如果在模拟中发生了情况 (a) 或 (b)， $D$ 已经给出了答案。
如果模拟达到了 $B$ 步（情况 c），根据我们对 $B_1$ 和 $B_2$ 的分析，这一定意味着 $M$ 已经陷入了一个永不向左的无限循环。因此，$D$ 停机并拒绝 (REJECT) 。

为什么 $D$ 是一个“判定器”？

$D$ 总会停机 ：$D$ 的模拟要么在 $B$ 步之内因情况 (a) 或 (b) 而停机，要么在 $B$ 步时因情况 (c) 而强制停机。$B$ 是一个根据输入 $\langle M, w \rangle$ 计算出来的具体、有限的数字。因此，$D$ 永远不会无限循环。
$D$ 总是正确的 ：
如果 $\langle M, w \rangle \in A$ ($M$ 确实向左移动了)，这个移动一定发生在 $M$ 停机或循环之前。如果它发生在 $B$ 步内，$D$ 会通过情况 (a) 接受。如果 $M$ 在 $B$ 步后才向左移动，那它一定是在 $B$ 步内进入了循环，但这是不可能的（因为我们的界限 $B$ 就是用来检测非左移循环的），所以向左移动一定发生在 $B$ 步内。
如果 $\langle M, w \rangle \notin A$ ($M$ 永不向左移动)，$M$ 只有两种可能：
$M$ 停机：$D$ 会在 $B$ 步内通过情况 (b) 拒绝。
$M$ 无限循环：$D$ 会在 $B$ 步时通过情况 (c) 检测到这个循环并拒绝。

因此，$D$ 是一个判定器，所以 $A$ 是 可判定的 (decidable) 。

例3：

$A_{TM}$是可识别的、不可判定的；

$\overline{A_{TM}}$是不可识别的、不可判定的。

quiz3：You will be asked to prove languages decidable or recognizable.

你将被要求证明某些语言是可判定的或可识别的

涉及内容：

可判定语言，对应Decider 判定机
可识别语言，对应Recognizer 识别机，Semi-decider 半判定机

这里注意，所有可判定语言都是可识别语言：

可判定的对L接受并停机，对非L拒绝并停机，所以总是停机
可识别的对L接受并停机，对非L拒绝或永不停止，不保证停机

4.3 对角化方法

According to COROLLARY 4.18 on textbook, some languages are not Turing-recognizable.

According to the diagonalization method, $L_{diag}$ and its complement is not recognizable.

Ch.5 可归约性

归约（Reduction）是计算理论和计算复杂性理论中的一个核心概念，它用于比较两个问题的难度。

如果一个问题A可归约到问题B，那么解A就不可能比解B更难，即A不超过B难，因为B的一个解给出了A的一个解。

比如说，在新的城市中认路的问题就可以归约为得到地图的问题，因为有了地图后认路就会变得非常简单。又比如说，从波士顿到巴黎的旅行问题可以归约到买这两个城市间的飞机票的问题，进而又可以归约到挣得买飞机票的钱的问题，进而又能进一步归约到找工作的问题。

在数学上，测量一个矩形的面积的问题可以归约到测量他的长和宽的问题；解线性方程组问题可以归约到求矩阵的逆问题。

在计算理论上，如果A可归约到B，且B可判定，那么A就是可判定的。同时，如果A是不可判定的，且可归约到B，那么B也是不可判定的。

通过规约，我们可以证明一个问题在计算上是否可解，这种证明方法就叫做可归约性（reducibility）。

5.1 证明不可判定

在第四章中，我们讲了如何判定一个语言是可判定的：如果一个问题能被Decider回答，那么这个问题就是Decidable（可判定的）。在本节中，我们将来证明一个问题是不可判定的：先证明另外一个问题是不可判定的，再将此问题归约到它。

5.2 证明停机问题不可判定

停机问题是：

\[ HALT_{TM} = \{\langle M, w \rangle | M \text{ 是一个图灵机, 且 } M \text{ 对输入 } w \text{ 停机}\} \]

和 $A_{TM}$（接受问题）进行对比：

$A_{TM}$ (接受问题): $\{\langle M, w \rangle | M$ 接受 $w \}$
它只关心 $M$ 是否接受 $w$。如果 $M$ 拒绝 $w$ 或者 $M$ 在 $w$ 上循环，这个 $\langle M, w \rangle$ 都不在 $A_{TM}$ 集合中。
$HALT_{TM}$ (停机问题): $\{\langle M, w \rangle | M$ 停机于 $w \}$
它关心 $M$ 是否停机（无论结果是接受还是拒绝）。
只有当 $M$ 在 $w$ 上循环时，这个 $\langle M, w \rangle$ 才不在 $HALT_{TM}$ 集合中。

举个例子：

假设我们有一个图灵机 $M$ 和输入 $w$。

M 在 w 上的行为	属于 ATM 吗?	属于 HALTTM 吗?
$M$接受$w$	是	是(因为接受也是一种停机)
$M$拒绝$w$	否	是(因为拒绝也是一种停机)
$M$在$w$ 上无限循环	否	否

所以，“停机问题”就是这样一个问题：

“是否存在一个万能的算法（判定器），你可以给它任何一个程序（图灵机 $M$）和它的一个输入（$w$），这个算法总能告诉你：‘这个程序在这个输入上会死机（无限循环）’还是‘它最终会停下来（给出接受或拒绝的结果）’？”

证明：

用反证法。

假设 $HALT_{TM}$ 是可判定的。如果这个假设成立，那么一定存在一个图灵机，我们把它叫做判定器R，可以判定 $HALT_{TM}$ 。

R的目标是判断M是否在w上停机：

如果M在w上最终会停机，R就接受
如果M在w上无限循环，R就拒绝

R总是会停机并给出接受或者拒绝的答案。

我们已知 $A_{TM}$ 是不可判定的，因此我们用R来构造一个判定 $A_{TM}$的机器S。

S的目标是判定是否属于 $A_{TM}$:

如果M接受w，则S必须接受
如果M拒绝w，则S必须拒绝。
如果M循环w，则S必须拒绝

当输入为时，S把交给R来判断；S等待R的回答，因为R是一个判定器，所以R会保证停机并给出答案。

R的回答有两种：

（1）如果M不接受w，即M在w上无限循环，或者M在w上停机且模拟结果是M拒绝w，这种情况下S会停机并拒绝。

（2）如果M接受w，即M在w上停机且模拟结果是M接受w，这种情况下S会停机并接受。

我们可以看到，无论R回答什么，S都会停机。如果模拟结果是M拒绝w，S停机并拒绝；如果模拟结果是M接受w，S停机并接受。因此S可以判定M是否接受w，即S是$A_{TM}$的判定器，换句话说，$A_{TM}$是可判定的。

然而，我们都知道，$A_{TM}$是不可判定的，因此上面出现了矛盾。该矛盾导致我们的假设：$HALT_{TM}$ 是可判定的不成立。从而我们可以反推出最终结论： $HALT_{TM}$ 是不可判定的。

5.3 证明L17不可判定

用刚才证明停机问题的方法，可以继续证明其他问题。

$L_{17} = \{X|X \text{ 是一个图灵机，它至少接受 17 个不同的输入字符串}\}$

证明：

用反证法。

假设 $L_{17}$ 是可判定的。如果这个假设成立，那么一定存在一个图灵机，我们把它叫做判定器 $R$，可以判定 $L_{17}$ 。

$R$ 的目标是判断图灵机 $X$ 是否接受至少 17 个字符串：

如果 $X$ 接受 $\ge 17$ 个字符串，$R$ 就接受 $\langle X \rangle$。
如果 $X$ 接受 $< 17$ 个字符串，$R$ 就拒绝 $\langle X \rangle$。

$R$ 总是会停机并给出接受或者拒绝的答案。

我们已知 $A_{TM}$ 是不可判定的，因此我们用 $R$ 来构造一个判定 $A_{TM}$ 的机器 $S$。

$S$ 的目标是判定 $\langle M, w \rangle$ 是否属于 $A_{TM}$ :

如果 $M$ 接受 $w$，则 $S$ 必须接受。
如果 $M$ 拒绝 $w$，则 $S$ 必须拒绝。
如果 $M$ 循环 $w$，则 $S$ 必须拒绝。

当输入为 $\langle M, w \rangle$ 时，S构造一个新图灵机D。D的设计为，当输入任意字符串x时，忽略输入的字符串x，然后再w上模拟运行M：

如果M接受w，则D接受x。
如果M拒绝或循环w，则D拒绝x。

构造完成后，$S$ 把D的结果交给 $R$ 来判断；$S$ 等待 $R$ 的回答，因为 $R$ 是一个判定器，所以 $R$ 会保证停机并给出答案。

$R$ 的回答有两种：

（1）如果M不接受w，即M在w上无限循环，或者M在w上停机但是模拟结果是M拒绝w，这种情况下D拒绝x，即D接收0个字符；因此R会判断0<17，从而R会拒绝D的结果，S会停机并拒绝。

（2）如果M接受w，即M在w上停机且模拟结果是M接受w，这种情况下D接收x，即D接收所有字符串的集合，该数量远大于17，因此R会判断>17，从而R会接收D的结果，S会停机并接收。

我们可以看到，无论 $R$ 回答什么，$S$ 都会停机。

如果 $M$ 不接受 $w$ (拒绝或循环)，$S$ 停机并拒绝。
如果 $M$ 接受 $w$，$S$ 停机并接受。

因此 $S$ 可以判定 $M$ 是否接受 $w$，即 $S$ 是 $A_{TM}$ 的判定器，换句话说，$A_{TM}$ 是可判定的。

然而，我们都知道，$A_{TM}$ 是不可判定的，因此上面出现了矛盾。该矛盾导致我们的假设：$L_{17}$ 是可判定的不成立。从而我们可以反推出最终结论： $L_{17}$ 是不可判定的。

5.4 证明M17不可判定且不可识别

$M_{17} = \{X|X \text{ 是一个图灵机，它至多接受 17 个不同的输入字符串}\}$

证明：

用反证法。

假设 $M_{17}$ 是可判定的。如果这个假设成立，那么一定存在一个图灵机，我们把它叫做判定器 $R$ ，可以判定 $M_{17}$ 。

$R$ 的目标是判断图灵机 $X$ 是否接受至多 17 个字符串：

如果 $X$ 接受 $\le 17$ 个字符串，$R$ 就接受 $\langle X \rangle$ 。
如果 $X$ 接受 $> 17$ 个字符串，$R$ 就拒绝 $\langle X \rangle$ 。

$R$ 总是会停机并给出接受或者拒绝的答案。

我们已知 $A_{TM}$ 是不可判定的，因此我们用 $R$ 来构造一个判定 $A_{TM}$ 的机器 $S$ 。

$S$ 的目标是判定 $\langle M, w \rangle$ 是否属于 $A_{TM}$ :

如果 $M$ 接受 $w$ ，则 $S$ 必须接受。
如果 $M$ 拒绝 $w$ ，则 $S$ 必须拒绝。
如果 $M$ 循环 $w$ ，则 $S$ 必须拒绝。

当输入为 $\langle M, w \rangle$ 时， $S$ 构造一个新图灵机 $D$。 $D$ 的设计为，当输入任意字符串 $x$ 时，忽略输入的字符串 $x$ ，然后再在 $w$ 上模拟运行 $M$：

如果 $M$ 接受 $w$，则 $D$ 接受 $x$。
如果 $M$ 拒绝或循环 $w$，则 $D$ 拒绝 $x$。

构造完成后，$S$ 把 $D$ 的结果交给 $R$ 来判断；$S$ 等待 $R$ 的回答，因为 $R$ 是一个判定器，所以 $R$ 会保证停机并给出答案。

$R$ 的回答有两种：

（1）如果 $M$ 不接受 $w$，即 $M$ 在 $w$ 上无限循环，或者 $M$ 在 $w$ 上停机但是模拟结果是 $M$ 拒绝 $w$，这种情况下 $D$ 拒绝 $x$，即 $D$ 接收0个字符；因此 $R$ 会判断 $0 \le 17$，从而 $R$ 会接受 $\langle D \rangle$ 的结果， $S$ 会停机并拒绝 $\langle M,w \rangle$。

（2）如果 $M$ 接受 $w$，即 $M$ 在 $w$ 上停机且模拟结果是 $M$ 接受 $w$，这种情况下 $D$ 接收 $x$，即 $D$ 接收所有字符串的集合，该数量远大于17；因此 $R$ 会判断 $> 17$，从而 $R$ 会拒绝 $\langle D \rangle$ 的结果， $S$ 会停机并接受 $\langle M, w \rangle$。

我们可以看到，无论 $R$ 回答什么，$S$ 都会停机。

如果 $M$ 不接受 $w$ (拒绝或循环)，$S$ 停机并拒绝。
如果 $M$ 接受 $w$ ，$S$ 停机并接受。

因此 $S$ 可以判定 $M$ 是否接受 $w$ ，即 $S$ 是 $A_{TM}$ 的判定器，换句话说，$A_{TM}$ 是可判定的。

然而，我们都知道，$A_{TM}$ 是不可判定的，因此上面出现了矛盾。该矛盾导致我们的假设：$M_{17}$ 是可判定的不成立。从而我们可以反推出最终结论： $M_{17}$ 是不可判定的。

证明M17是不可识别的

证明：

假设 $M_{17}$ 是可识别的。

$\overline{M_{17}} = L_{18} = \{X | X \text{ 接受至少 18 个字符串}\}$

我们必须构造一个Recognizer R18，R18会记录输入的字符串x，如果接收的字符串数量达到18就立刻停机并接收x：

如果X接收至少18个字符串，那么R18将会停机并接收X。
如果X接收少于18个字符串，那么R18将会无限循环。

因此L18是可识别的，即M17的补集是可识别的。由于我们假设M17是可识别的，现在M17的补集也是可识别的，根据定理，M17一定是可判定的。

然而我们已经证明M17是不可判定的，因此假设矛盾，即M17是不可识别的。

5.5 证明T不可判定

\[ T = \{ \langle M \rangle \mid M \text{ 是一个图灵机，当且仅当它接受 } w \text{ 时，也接受 } w^R \} \]

其中$w^R$表示将字符串 ( w ) 反转后的结果。

证明：

用反证法。

假设 $T$ 是可判定的。如果这个假设成立，那么一定存在一个图灵机，我们把它叫做判定器 $R$ ，可以判定 $T$ 。

$R$ 的目标是判断图灵机 $X$ 是否满足“每当它接受 $w$ 时，它也接受 $w^R$”：

如果 $X$ 满足该属性 (即 $w \in L(X) \implies w^R \in L(X)$)，$R$ 就接受 $\langle X \rangle$ 。
如果 $X$ 不满足该属性 (即 $\exists w$ 使得 $w \in L(X)$ 但 $w^R \notin L(X)$)，$R$ 就拒绝 $\langle X \rangle$ 。

$R$ 总是会停机并给出接受或者拒绝的答案。

我们已知 $A_{TM}$ 是不可判定的，因此我们用 $R$ 来构造一个判定 $A_{TM}$ 的机器 $S$ 。

$S$ 的目标是判定 $\langle M, w \rangle$ 是否属于 $A_{TM}$ :

如果 $M$ 接受 $w$ ，则 $S$ 必须接受。
如果 $M$ 拒绝 $w$ ，则 $S$ 必须拒绝。
如果 $M$ 循环 $w$ ，则 $S$ 必须拒绝。

当输入为 $\langle M, w \rangle$ 时， $S$ 构造一个新图灵机 $D$ 。 $D$ 的设计为，当输入任意字符串 $x$ 时，$D$ 首先在 $w$ 上模拟运行 $M$ ：

如果 $M$ 接受 $w$ ，则 $D$ 接着检查 $x$ 。如果 $x = \text{"ab"}$，$D$ 接受 $x$；否则，$D$ 拒绝 $x$。
如果 $M$ 拒绝或循环 $w$ ，则 $D$ 拒绝 $x$ (或因 $M$ 循环而循环)。

构造完成后，$S$ 把 $\langle D \rangle$ 的结果交给 $R$ 来判断；$S$ 等待 $R$ 的回答，因为 $R$ 是一个判定器，所以 $R$ 会保证停机并给出答案。

$R$ 的回答有两种：

（1）如果 $M$ 不接受 $w$ ，即 $M$ 在 $w$ 上无限循环，或者 $M$ 在 $w$ 上停机但是模拟结果是 $M$ 拒绝 $w$ ，这种情况下 $D$ 不接受任何字符串，即 $D$ 接收0个字符 ($L(D) = \emptyset$)；因此 $R$ 会判断 $D$ 满足 $T$ 的属性 (因为条件“每当 $D$ 接受...”是空泛为真的)，从而 $R$ 会接受 $\langle D \rangle$ 的结果， $S$ 会停机并拒绝 $\langle M,w \rangle$ 。

（2）如果 $M$ 接受 $w$ ，即 $M$ 在 $w$ 上停机且模拟结果是 $M$ 接受 $w$ ，这种情况下 $D$ 只接收 "ab"，即 $L(D) = \{\text{"ab"}\}$。$D$ 接受 "ab"，但它不接受 "ab" 的反转 "ba"；因此 $R$ 会判断 $D$ 不满足 $T$ 的属性，从而 $R$ 会拒绝 $\langle D \rangle$ 的结果， $S$ 会停机并接受 $\langle M, w \rangle$ 。

我们可以看到，无论 $R$ 回答什么，$S$ 都会停机。

如果 $M$ 不接受 $w$ (拒绝或循环)，$S$ 停机并拒绝。
如果 $M$ 接受 $w$ ，$S$ 停机并接受。

因此 $S$ 可以判定 $M$ 是否接受 $w$ ，即 $S$ 是 $A_{TM}$ 的判定器，换句话说，$A_{TM}$ 是可判定的。

然而，我们都知道，$A_{TM}$ 是不可判定的，因此上面出现了矛盾。该矛盾导致我们的假设：$T$ 是可判定的不成立。从而我们可以反推出最终结论： $T$ 是不可判定的。

5.6 证明奇图灵机不可识别

Call a Turing Machine that accepts input strings in binary odd if it only accepts binary inputs that end in 1. Consider the language

\[ T = \{ \langle M \rangle \mid M \text{ is an odd Turing machine} \} \]

Prove that T is not recognizable.

证明：

用反证法。

假设 $T$ 是可识别的 (recognizable)。如果这个假设成立，那么一定存在一个图灵机，我们把它叫做识别器 $R$ ，可以识别 $T$ 。

$R$ 的目标是判断图灵机 $X$ 是否是一个 "odd" TM：

如果 $X$ 是 "odd" TM (即 $X$ 只接受以 '1' 结尾的二进制串)，$R$ 就停机并接受 $\langle X \rangle$ 。
如果 $X$ 不是 "odd" TM (即 $X$ 接受了至少一个不以 '1' 结尾的串)，$R$ 就不接受 $\langle X \rangle$ (它可能停机拒绝，也可能无限循环)。

$R$ 只在输入属于 $T$ 时保证停机并接受。

我们已知 $\overline{A_{TM}}$ 是不可识别的。因此我们用 $R$ 来构造一个识别 $\overline{A_{TM}}$ 的机器 $S$。

($\overline{A_{TM}} = \{\langle M, w \rangle \mid M \text{ 不接受 } w\}$)

$S$ 的目标是识别 $\langle M, w \rangle$ 是否属于 $\overline{A_{TM}}$ :

如果 $M$ 不接受 $w$ (拒绝或循环)，则 $S$ 必须接受。
如果 $M$ 接受 $w$ ，则 $S$ 必须不接受 (拒绝或循环)。

当输入为 $\langle M, w \rangle$ 时， $S$ 构造一个新图灵机 $D$ 。 $D$ 的设计为，当输入任意字符串 $x$ 时：

$D$ 首先在 $w$ 上模拟运行 $M$ 。
如果 $M$ 接受 $w$ ：
$D$ 接受 $x$ (无论 $x$ 是什么)。
如果 $M$ 拒绝或循环 $w$ ：
$D$ 检查 $x$ 。如果 $x$ 以 '1' 结尾，$D$ 接受 $x$ ；否则，$D$ 拒绝 $x$ (或因 $M$ 循环而循环)。

构造完成后，$S$ 把 $\langle D \rangle$ 的结果交给 $R$ 来判断；$S$ 运行 $R(\langle D \rangle)$，并执行与 $R$ 相同的操作（如果 $R$ 接受， $S$ 接受；如果 $R$ 循环/拒绝， $S$ 循环/拒绝）。

$R$ 的行为有两种：

（1）如果 $M$ 不接受 $w$ (拒绝或循环)：

在这种情况下，$D$ 的模拟永远不会进入“$M$ 接受 $w$”的分支。$D$ 的行为将由第二分支决定：它只接受以 '1' 结尾的字符串。
(如果 $M$ 循环，$D$ 也会在所有输入 $x$ 上循环，因此 $L(D) = \emptyset$。空语言也满足 "只接受以 '1' 结尾的串"。)
无论哪种情况，$D$ 都是一个 "odd" TM，即 $\langle D \rangle \in T$。
因为 $R$ 是 $T$ 的识别器，$R$ 会停机并接受 $\langle D \rangle$ 的结果。
$S$ 会停机并接受 $\langle M,w \rangle$。

（2）如果 $M$ 接受 $w$：

在这种情况下，$D$ 的模拟会进入“$M$ 接受 $w$”的分支。$D$ 将接受所有输入 $x$。
$D$ 的语言 $L(D) = \Sigma^*$ (所有字符串的集合)。
$D$ 不是一个 "odd" TM，因为它接受了不以 '1' 结尾的串 (例如 "0", "10", $\epsilon$)。即 $\langle D \rangle \notin T$。
因为 $R$ 是 $T$ 的识别器，$R$ 会不接受 $\langle D \rangle$ 的结果 (它可能拒绝或循环)。
$S$ 也会不接受 $\langle M, w \rangle$。

我们可以看到，$S$ 的行为完美地匹配了 $\overline{A_{TM}}$ 的定义：

如果 $M$ 不接受 $w$ ，$S$ 停机并接受。
如果 $M$ 接受 $w$ ，$S$ 不接受 。

因此 $S$ 可以识别 $\overline{A_{TM}}$ ，即 $S$ 是 $\overline{A_{TM}}$ 的识别器。

然而，我们都知道，$\overline{A_{TM}}$ 是 不可识别的 ，因此上面出现了矛盾。该矛盾导致我们的假设：$T$ 是可识别的不成立。从而我们可以反推出最终结论： $T$ 是不可识别的。

5.7 可计算函数

例题

Show that if $A$ is Turing recognizable and $A \le_m \overline{A}$, then $A$ is decidable.

证明：

我们的目标是证明 $A$ 是可判定的 (Decidable)，这意味着我们需要构造一个决策器 (Decider) $D_A$。这个决策器 $D_A$ 必须在所有输入 $w$ 上停机，并且：

如果 $w \in A$，则 $D_A$ 接受 $w$。
如果 $w \notin A$，则 $D_A$ 拒绝 $w$。

根据题目，我们已经知道$A$ 是图灵可识别的 (Turing-recognizable)，换句话说，存在一个图灵机（识别器）$R_A$，如果 $w \in A$，$R_A(w)$ 会停机并接受；如果 $w \notin A$，$R_A(w)$ 可能会停机拒绝，也可能会 无限循环 。

对于条件$A \le_m \overline{A}$，我们可以得知存在一个总可计算函数$f$ 满足：$w \in A \iff f(w) \in \overline{A}$。

我们可以把这个关系拆解为两个方向：

如果 $w \in A$，那么 $f(w) \in \overline{A}$（即 $f(w) \notin A$）。
如果 $w \notin A$，那么 $f(w) \notin \overline{A}$（即 $f(w) \in A$）。

我们利用 $R_A$ 和 $f$ 来构造决策器 $D_A$。

$D_A$ 的算法描述如下：

计算 $f(w)$。此步骤 保证停机 ，因为 $f$ 是总可计算函数。
并行运行以下两个计算：运行 $R_A(w)$ 与运行 $R_A(f(w))$

当其中一个计算停机并接受：

如果$R_A(w)$接受，则 $D_A$ 接受 $w$ 并停机。
如果$R_A(f(w))$接受，则 $D_A$ 拒绝 $w$ 并停机。

我们分两种情况讨论，来证明两个计算中至少有一个会停机接受：

假设 $w \in A$，根据已知条件，识别器 $R_A(w)$必定会停机并接受 。因此，$D_A$ 必定会停机。
假设 $w \notin A$，根据已知条件，识别器$R_A(f(w))$必定会停机并接受 。因此，$D_A$ 必定会停机。

因此，$D_A$ 总是会停机 。

我们再次分情况讨论，并验证 $D_A$ 的输出是否正确：

假设$w \in A$，我们已经知道 $R_A(w)$会停机接受，并且知道$w \in A \implies f(w) \notin A$。根据已知条件，$R_A(f(w))$永远不会停机接受（它可能拒绝或循环）。因此，在并行执行中， 必定是计算 1 先停机接受 。
假设 $w \notin A$，我们已经知道 $f(w) \in A$，所以 $R_A(f(w))$会停机接受。根据已知条件，因为 $w \notin A$，$R_A(w)$永远不会停机接受。因此，在并行执行中， 必定是计算 2 先停机接受 。

因此，我们成功构造了一个图灵机 $D_A$，它在所有输入 $w$ 上 总是停机 ，并且能正确地判断 $w$ 是否属于 $A$。

因此，$D_A$ 是 $A$ 的一个决策器，这证明了 $A$ 是 可判定的 。

Ch.6 P类

从本章开始我们进入复杂性理论的议题。同时注意这章开始我的笔记中的章节序号和计算理论原书中的章节序号将不再同步，我会按照我个人需要整理序号。

P vs NP，中文中也称为P/NP问题，是理论计算机科学中计算机复杂度理论领域至今为解决的问题。2000年，美国CMI数学研究所发布了千禧年大奖难题，解题总奖金700万美元，其中第一个就是P/NP问题。

复习一下P和NP的定义：

P=成员资格可以快速地判定的语言类
NP=成员资格可以快速地验证的语言类

千禧年大奖难题的七个问题如下：

P/NP问题
霍奇猜想
庞家莱猜想（唯一目前已经被证明的问题）
黎曼猜想
杨-米尔斯存在性与质量间隙
纳维-斯托克斯存在性与光滑性
贝赫和斯维讷通-戴尔猜想

简单来说，P/NP问题就是在问：

P是否等于NP？

这个问题可能看起来是千禧年七大问题中描述最简单的，但很多人相信该问题将会是千禧年七大问题中最后一个解决的。

如果$P=NP$，那么几乎所有现代加密（RSA、ECC）都会瞬间失效，大量NP-Hard问题都会被线性时间甚至更快解决，数学自动定理证明、AI、优化等都将革命性改变。但如果想证明$P \ne NP$，却又非常困难，这本质上是对所有算法的终极否定，类似于试图证明“永远找不到一个更好的方法”，这是一种不可计算的结构或者说本质困难的证明。

在过去的几十年里，研究者证明了我们目前已知的很多看似强大的数学工具都无法解决P vs NP问题。换句话说，面对P vs NP问题，我们连入口方向都没有，甚至不知道应该使用哪种数学工具来突破。

6.1 时间复杂性

为什么要度量时间复杂性呢？因为假如一个问题的求解在理论上是可判定的，但是解决它要非常多的时间，甚至超过宇宙大爆炸到现在，那么这个问题即使可判定，我们也不可能去用现有方法求解。因此，我们必须度量求解问题所需时间。

令$M$ 是一个确定型图灵机（也就是普通的电脑程序，给定输入，输出是确定的），令 $f(n)$ 是M的时间复杂度函数 ，其中：

输入是 $\mathbb{N}$（非负整数，代表输入字符串的长度 $n$）
输出是 $\mathbb{N}$（非负整数，代表步数）

换句话说，$f(n)$ 是机器 $M$ 在处理任何长度为 $n$ 的输入时，所经过的 最大步数 。这里我们分析的是最坏情况（worst case）。

除此之外，我们还可能分析平均情况（average case）。

大O

设 $f, g: \mathbb{N} \to \mathbb{R}^+$。我们称 $f(n) = O(g(n))$，当且仅当存在正常数 $c$ 和 $n_0$，使得对于所有 $n \ge n_0$，都有：

\[ f(n) \le c \cdot g(n) \]

换句话说，只要 $n$ 足够大（超过 $n_0$），并且允许把 $g(n)$ 放大 $c$ 倍，$g(n)$ 就能永远“盖住” $f(n)$。这意味着 $f$ 的增长率不超过 $g$。此时，我们称$g(n)$是$f(n)$的渐进上界（Asymptotic Upper Bound）。

这里的渐进的含义是：我们只关心 $n \to \infty$ 时的趋势，忽略 $n$ 很小时的情况（由 $n_0$ 保证）。

小o

小o记法和大O的区别在于，小o中$f$的增长速度要严格慢于$g$。换言之， $f(n) = o(g(n))$ 意味着对于任何实数$c \gt 0$，存在一个数$n_0$，使得对所有$n \ge n_0, f(n) < c g(n)$

我们要判断 $f(n) = o(g(n))$，通常用极限法来判断：

\[ \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0 \]

当 $n$ 趋向无穷大时，$g(n)$ 变得相对于 $f(n)$ 无限大，导致它们的比值趋近于 0，此时我们说 $f(n) = o(g(n))$。

6.2 多项式时间

我们可以把下列天梯记下来，用来快速判断时间复杂度关系，这在实际编程和思考问题时很有用：

方向：从上到下，增长速度 $\uparrow$ (越往下越快)。

Constant Time 常数级 - $O(1)$
Ex: $1, 100, 5000$
Double Logarithmic - $O(\log \log n)$
Ex: $\log(\log n)$
注：增长极慢，几乎看作常数。
Logarithmic 对数级 - $O(\log n)$
Ex: $\ln n, \log_2 n$
Polylogarithmic - $O((\log n)^c)$
Ex: $(\log n)^2, (\log n)^{10}$
注：比 $O(n)$ 慢，但比 $O(\log n)$ 快。
Fractional Power / Sublinear - $O(n^c), 0 < c < 1$
Ex: $n^{0.5} (\text{i.e., } \sqrt{n}), n^{1/3}$
注：根号永远胜过对数。
Linear - $O(n)$
Linearithmic / Quasilinear - $O(n \log n)$
Ex: Merge Sort, Heap Sort
Polynomial 多项式级 - $O(n^k), k \ge 1$
Ex: $n^2$ (Quadratic), $n^3$ (Cubic)
注：这是“有效算法” (Class P) 的边界。
Quasi-polynomial - $n^{\text{polylog}(n)}$
Ex: $n^{\log n}$, $2^{(\log n)^c}$
特征：底数是 $n$ 但指数是对数，或者底数是 $2$ 但指数是 $\text{polylog}$。
Strictly Sub-exponential - $2^{o(n)}$
- Ex: $h(n) = 2^{\sqrt{n}}$, $2^{n^{1/3}}$
- 特征：比多项式快，但还没快到 $2^n$。通常形式为 $2^{n^\epsilon}$ ($0 < \epsilon < 1$)。
- Exponential 指数级 - $O(c^n), c > 1$
- Ex: $1.01^n, 2^n, e^n, 3^n$
- 特征：底数 $c$ 越大增长越快。这是“难解问题” (Intractable) 的典型区域。
- Factorial - $O(n!)$
- Ex: 排列问题 (Permutations)
- 注：根据斯特林公式，$n! \approx (n/e)^n$，增长极快。
- Super-exponential - $O(n^n)$
- Ex: $n^n, 2^{2^n}$ (Double Exponential)
- 注：阿克曼函数 (Ackermann function) 就在这个深渊里。

我们一般会关注两个分界点：

Polynomial 多项式级
Exponential 指数级

如果一个问题有多项式算法，那么只要电脑足够快，我们迟早能算出结果。对于超过多项式级的问题（super-polynomial），我们通常认为它在实际应用中是不可解的。

而指数级则常用来衡量加密算法是否安全。我们一般认为，对于一个可以在指数级时间内（sub-exponential）解开的密码，我们通常认为它在实际应用中是不安全的。

换句话说：

Super-polynomial：实际应用中不可解
Sub-exponential：实际应用中不安全

例题

我们对下列函数进行排序：

极慢增长 (对数级):
$f(n) = \log \log n$ （增长极慢，比 $\log n$ 还慢）
多项式及以下 (Polynomials & Roots):
$d(n) = 2\sqrt{n} + 400,000 \approx O(n^{0.5})$
$g(n) = 2n^{2/3}\log^2 n \approx O(n^{0.66...})$ （注意：$n^{2/3}$ 的指数 $0.66$ 大于 $n^{0.5}$）
$b(n) = 7n \log n \approx O(n^{1+\epsilon})$ （比纯线性大，比平方小）
$a(n) = 3n^2 + 7 \approx O(n^2)$
$e(n) = 10n^2 - 40 \approx O(n^2)$
(注：$a$ 和 $e$ 同级，通常怎么排都可以，因为 $O(a) = O(e)$)
准多项式 / 次指数 (Quasi-polynomial / Sub-exponential):
这里有两个棘手的函数：$l(n) = n^{\log n}$ 和 $h(n) = 2^{\sqrt{n}}$。
变换 $l(n)$：$n^{\log n} = 2^{(\log n)^2}$。
比较 $l(n)$ 和 $h(n)$：比较指数部分 $(\log n)^2$ 和 $\sqrt{n}$。当 $n$ 很大时，$\sqrt{n}$ 远大于 $(\log n)^2$。
因此： $n^2 < l(n) < h(n)$ 。
指数级 (Exponential):
$j(n) = e^n * n^{23} \approx O(e^n)$ （底数 $e \approx 2.718$）
$c(n) = 3^n$ （底数 $3$）
因为 $e < 3$，所以 $j(n) < c(n)$。
阶乘与双重指数 (Factorial & Doubly Exponential):
$i(n) = n!$ （根据 Stirling 公式，约等于 $n^n$，比 $3^n$ 快得多）
$k(n) = 2^{2^n}$ （双重指数，增长极其恐怖，排在最后）

最终排序结果：

\[ f \le d \le g \le b \le a = e \le l \le h \le j \le c \le i \le k \]

.

6.3 P类问题

P类问题（Polynomial Time） 就是指可以在多项式级及以内完成运行的算法，比如：

$O(1)$
$O(\log n)$
$O(\sqrt{n})$
$O(n)$
$O(n^2)$
$O(n^{100})$

在计算机科学中，P类通常被认为是有效率的算法（Efficient Algorithm）。

我们可如此记忆：如果一个问题的最优已知算法在最坏情况下的时间复杂度是

\[ O(n^k) \]

其中$k$是某个常数、$n$是输入规模，那么这个问题属于 P 类问题 。

6.4 多项式等价性

计算理论中存在多种计算模型（如单带图灵机、多带图灵机、随机存取机等）。虽然它们的架构不同，但它们之间通常是“多项式等价”的。即：一个模型能做的事，另一个模型也能做，且模拟所需的额外时间开销仅为多项式级别。因此， P 类是稳健的 (Robust) 。

换句话说，$P$ 类的范围不依赖于具体的计算模型（只要是确定型的）。这证明了 $P$ 是一个客观存在的、数学上定义良好的类，而不是某个特定机器的人造产物。

$P$ 是确定型单带图灵机在多项式时间内可判定的语言类：

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

其包含了所有能在 $n^1, n^2, n^3 \dots$ 等时间复杂度内解决的问题。

这里对P的讨论体现出了两个重要性：

$P$ 类在数学上是 不变的 ，它是一个不受具体实现细节干扰的稳定集合。
$P$ 类大致对应于计算机上实际可解的问题。

有一个很常见的问题是：如果一个算法是 $n^{100}$，它虽然属于 P，但实际根本跑不动，这还能叫实际可解吗？”

书中对于该问题的解释是：

实际上很少有属于 $P$ 的问题只能用 $n^{100}$ 这种极端算法解决。通常一旦属于 $P$，往往存在 $n^2$ 或 $n^3$ 的算法。
如果为一个原本看似需要指数时间的问题找到了多项式算法（哪怕是 $n^{100}$），这标志着我们 洞察到了问题的数学结构 。而这种从指数到多项式的跨越是质变的。

换句话说，P和NP的讨论是一种质的讨论。哪怕一个算法是 $n^{100}$，只要它属于P，那么科学家通常就能迅速优化算法，降低其幂次（例如从 $n^{100}$ 优化到 $n^3$），最终使其达到实用的程度。因此将多项式时间作为可解性的标准，在历史上已被证明是非常有用的经验法则。

6.5 证明是P

证明属于P其实就是找到一个确定性算法（Deterministic Algorithm），并且这个算法的运行时间是输入规模的 多项式函数 ，那么这个判定问题就属于复杂度类 $\mathbf{P}$。

PATH问题

书中举的PATH问题其实就是判断图的连通性。给定一个有向图 $G$，其中包含一组结点的集合和一组边的集合。同时给定图中两个特定的结点：起点 $s$ 和终点 $t$。我们需要判定是否存在一条从 $s$ 到达 $t$ 的有向路径。

形式化地，该语言定义为：

\[ PATH = \{ \langle G, s, t \rangle \mid G \text{ 是包含从 } s \text{ 到 } t \text{ 的有向路径的有向图} \} \]

图的规模通常由结点数 $m$ 来衡量。

针对该问题的蛮力算法（Brute-force algorithm）是通过遍历 $G$ 中所有可能的路径来寻找是否存在连接 $s$ 和 $t$ 的路径。由于一条简单路径的长度不会超过图中结点的总数 $m$，暴力法会尝试枚举长度在 $m$ 以内的所有结点序列。然而，在包含 $m$ 个结点的图中，可能的路径组合数量大致是 $m^m$ 的量级。这是一个指数级的增长，意味着随着图规模的略微增加，计算所需的时间将呈爆炸式增长。因此，这种蛮力算法无法在多项式时间内完成，不是一个有效的解决方案。

为了证明 $PATH$ 属于 P 类（多项式时间可解），我们采用一种基于广度优先搜索（BFS）思想的标记算法。该算法的核心在于迭代地标记从起点 $s$ 出发可达的所有结点。算法首先标记起点 $s$，随后进入一个循环过程：扫描图中的所有边，若发现某条边从一个“已标记”结点指向一个“未标记”结点，则将后者也进行标记。这个过程重复进行，直到无法再标记新的结点为止。

由于图中总共只有 $m$ 个结点，且每一轮有效的循环至少会标记一个新的结点，因此循环执行的次数不会超过 $m$ 次。算法的每一步都在多项式时间内完成，总运行时间是关于图规模 $m$ 的多项式。

P类解法如下：

算法 M (输入：有向图 G, 起点 s, 终点 t)

    1. 初始化：将结点 s 标记为“已访问”。

    2. 循环执行：重复以下步骤，直到某次循环中没有新的结点被标记：
         遍历图 G 的所有边 (a, b)：
             若结点 a 已被标记 且 结点 b 未被标记：
                 将结点 b 标记为“已访问”。

    3. 判定：
         若结点 t 被标记：
             接受 (ACCEPT)
         否则：
             拒绝 (REJECT)

因此$PATH \in P$。

RELPRIME问题

书中提到的另一个RELPRIME问题其实就是互素问题，旨在判定两个自然数 $x$ 和 $y$ 是否互素（即最大公约数为 1）：

\[ RELPRIME = \{<x,y>|x与y互为素数\} \]

形式化地，如果 $\gcd(x, y) = 1$，则算法接受该输入。这里的gcd是最大公约数（greatest common divisor）的缩写。

这里注意，该问题对输入规模的定义是一个数字的输入规模而非其数值本身的大小。比如说，如果输入是n，那么输入的将是一个长度为n的二进制数，并且其数值范围将是：

\[ 2^{n-1} \le x < 2^n \]

这里说明一下这个数值范围的含义：其最高位必须是1，因此下限是$2^{n-1}$，代表一个 $n$ 位的数，其二进制表示是 $1$ 后面跟着 $(n-1)$ 个 $0$（$10\dots0_2$）。这是所有恰好需要 $n$ 位表示的数中最小的一个。例如，当 $n=4$ 时，$2^{4-1} = 2^3 = 8$ (二进制 $1000_2$)。同时，其上限$2^n$是因为对于一个$(n+1)$位的数，其二进制表示是$1$后面跟着$n$个$0$（$10\dots0_2$）。所有$n$位的数都小于它。例如，当$n=4$时，$2^4 = 16$ (二进制$10000_2$).

解决该问题的蛮力算法是尝试搜索这两个数的所有公因子。如果遍历从 2 到 $\min(x, y)$ 的所有整数来检查整除性，这种方法在计算复杂性上是不可行的。因为对于一个长度为 $n$ 位的二进制数，其数值大小约为 $2^n$。如果算法的运行时间与数值大小成正比，那么相对于输入长度 $n$ 而言，该算法的运行时间就是指数级的 $O(2^n)$。这种基于数值大小的线性搜索被称为“伪多项式时间”，本质上属于指数时间算法。

为了证明 $RELPRIME$ 属于 P 类，我们使用经典的欧几里得算法（Euclidean algorithm），或者说辗转相除法：利用 $x \pmod y$ 的性质来递归求解最大公约数。分析表明，在欧几里得算法中，每经过两次递归迭代（或两次交换操作），参数的数值至少会减少一半。这意味着算法的迭代次数与 $\log(\text{数值})$ 成正比。由于 $\log(\text{数值})$ 正好等同于输入的二进制长度，因此该算法的运行时间与输入长度成线性或多项式关系，证明了该问题可以在多项式时间内解决。

P类解法如下：

算法 R (输入：自然数 x, 自然数 y)

    1. 调用子程序 E(x, y) 计算最大公约数，过程如下：
         算法 E：
         重复执行，直到 y = 0：
             令 x = x mod y
             交换 x 和 y 的值
         输出 x

    2. 判定子程序 E 的输出结果：
         若 E 的输出为 1：
             接受 (ACCEPT)
         否则：
             拒绝 (REJECT)

因此$RELPRIME \in P$。

2COLOR问题

输入：无向图 $G=(V,E)$（用邻接表或邻接矩阵都行）

输出：

若图可以2-染色，则给出每个顶点的颜色（例如：RED / BLUE）
若不可以2-染色，则报告“不是二分图 / 不能2-染色”

算法：

(1) 每个点一开始都是“未着色”。

(2) 对图的每个连通分量做一次 BFS：

随便选该分量里的一个未着色点，着色为 RED；

从它开始 BFS:

对当前点 u 的每个邻居 v：

若 v 未着色，则给 v 赋与 u 不同的颜色，并入队；
若 v 已着色，且颜色与 u 相同 ⇒ 冲突 ⇒ 不能2染色，算法结束返回失败。

(3) 所有点都检查完，如果没有冲突，则成功返回颜色数组。

Ch.7 NP类

在P类问题讨论中我们可以看到，许多问题可以避免暴力解法来获得多项式时间解法。这里要注意，只要一个问题有多项式解法，那么这个问题就是P类问题，无论你最终使用什么解法来求解。

然而，有许多问题到现在为止都还没有找到多项式解法。换句话说，许多问题到现在为止都还没有找到可以避免暴力解法的算法。目前数学还未能解释这些问题是否有固有难算的性质。

7.1 NP类问题

许多问题可以在多项式时间内求解（P类问题），但还有一些非常重要的问题，我们努力了几十年仍然找不到多项式时间算法。这些问题并不是没人研究，而是 可能就没有多项式时间算法 ，也可能 我们现在还不知道如何找到 。

很多难题之间的复杂性是相关联的：

解决一个难题的多项式算法，可能可以用来解决另一个难题。

这一点对理解NP-Complete非常重要，不过本节我们先讨论NP类。

简单来说，如果说P类问题就是在探寻能在多项式时间内求解的问题，那么：

NP类问题是能在多项式时间内验证的问题。

即P类问题是容易求解的问题，NP类问题是不一定容易求解但容易检查结果的问题。

NP问题的核心特征是多项式可验证性（Polynomial Verifiability）。我们通过下面的HAMPATH问题来进一步了解。NP不是“非多项式”，而是Nondeterministic Polynomial time （非确定性多项式时间），即：

NP类是可以在多项式时间内验证解是否正确的问题集合。

7.2 HAMPATH问题

HAMPATH（Hamiltonian Path，哈密顿路径）问题是图论中的一个经典问题。给定一个有向图 $G$ 和图中的两个特定节点 $s$（起点）和 $t$（终点），判断是否存在一条从 $s$ 到 $t$ 的路径，使得这条路径 恰好经过图 $G$ 中的每一个节点一次 ：

\[ \text{HAMPATH} = \{ \langle G, s, t \rangle \mid G \text{ 中存在从 } s \text{ 到 } t \text{ 的哈密顿路径} \} \]

简单来说： 就像一个旅行推销员要从城市 $s$ 出发到城市 $t$，且必须拜访所有其他城市，但每个城市只能去一次。

HAMPATH 问题之所以重要，是因为它是一个典型的 NP 完全问题（NP-Complete） 。我们等会儿讨论NP-Complete，回到这个问题本身，该问题是理论计算机科学中，证明很多其他复杂问题属于 NP 完全的基石之一。目前为止，没有人知道一个能在多项式时间内（即“快速”）找到哈密顿路径的算法。 求解 HAMPATH 问题的已知最佳算法需要指数时间（例如 $O(2^n)$ 或 $O(n!)$），对于大规模的图来说是不可行的。

尽管 HAMPATH 很难在多项式时间内求解，但它的解可以在多项式时间内被验证：

如果有人（我们称之为“证明者”）提供了一条 声称是哈密顿路径的序列 $P$* ，我们（“验证者”）可以在极短的时间内（多项式时间）检查 *$P$ 是否真的是一个有效的哈密顿路径：

检查起点和终点： 路径 $P$ 是否从 $s$ 开始，到 $t$ 结束？ $\rightarrow O(1)$
检查边的存在性： 路径 $P$ 中相邻的节点之间，其对应的边是否在图 $G$ 中真实存在？ $\rightarrow O(n)$ (其中 $n$ 是节点数)
检查节点唯一性： 路径 $P$ 是否恰好包含图 $G$ 中的所有节点，且每个节点只出现了一次？ $\rightarrow O(n)$

总复杂度： $O(1) + O(n) + O(n) = O(n)$。

因为 $O(n)$ 是多项式时间，所以 HAMPATH 问题属于 NP 问题。

7.3 COMPOSITES问题

COMPOSITES （合数）问题，它是一个经典的多项式可验证的例子：

\[ \text{COMPOSITES} = \{ x \mid x = pq, \text{ 整数 } p, q > 1 \} \]

找到一个大整数的因子 $p$ 和 $q$ 是一个著名的难题（目前没有已知的多项式时间算法）。但是如果有人声称 $x$ 是一个合数，他只需要提供 $x$ 的一个因子 $p$（满足 $1 < p < x$）。

验证机只需要在多项式时间内完成两个简单的检查：

检查 $p$ 是否大于 1。
检查 $p$ 能否整除 $x$ (即 $x \bmod p = 0$)。

验证过程极快，因此 COMPOSITES 问题是 多项式可验证的 ，属于 NP 类。

7.4 证明是NP

Verifier 验证机

为了严谨地定义“多项式可验证”，书中引入了 验证机（verifier） 的概念。

语言 $A$ 的验证机是一个算法 $V$，这里：

\[ A=\{w \mid \text{对某个字符串 } c, V \text{ 接受 } \langle w, c \rangle \} \]

因为只根据 $w$ 的长度来度量验证机的时间，所以多项式时间验证机 (polynomial time verifier) 在 $w$ 的长度的多项式时间内运行。若语言 $A$ 有一个多项式时间验证机，则称它为多项式可验证的 (polynomially verifiable)。

验证机利用额外的消息（在定义 7.15 中用符号 $c$ 表示）来验证字符串 $w$ 是 $A$ 的成员。该信息称为 $A$ 的成员资格证书 (certificate) 或 证明 (proof) 。注意，对于多项式时间验证机，证书具有多项式的长度（$w$ 的长度），因为这是该验证机在它的时间界限内所能访问到的全部信息长度。把该定义应用到语言 HAMPATH 和 COMPOSITES 上：

对于 HAMPATH 问题，字符串 $\langle G, s, t \rangle \in \text{HAMPATH}$ 的证书就只是一条从 $s$ 到 $t$ 的哈密顿路径。
对于 COMPOSITES 问题，合数 $x$ 的证书只是它的一个因子。

在这两种情况下，当把证书交给验证机以后，它就能在多项式时间内检查输入是否在语言中。

简单来说，用验证机验证一个问题是否属于NP一般有以下步骤：

设定一个C，C可以是一个方案、一个子集等。C是证明问题“对”或者“是”的证据。
设立一个Verifier，通过一系列Verification Steps，来决定Accept或是Reject C
如果Verification Steps都在Polynomial Time内，那么该问题就是NP。

NTM

我们也可以用Verifier来证明一个问题是NP问题。

定理：

一个语言在NP中，当且仅当它能被某个非确定性多项式时间图灵机（Non-deterministic Turing Machine, NTM）判定。

能被NTM判定，和通过Verifier证明，在数学上是等价的。

证明一个语言属于NP，既可以用Verifier，也可以用NTM，但相比较而言Verifier更简单。我们来看几道使用Verifier证明问题属于NP的例子。

SUBSET-SUM问题

证明SUBSET-SUM是NP

SUBSET-SUM：给定一个有限集 $S = \{x_1, x_2, \ldots, x_n\}$，其中 $x_i$ 都是正整数，以及一个目标正整数 $t$。SUBSET-SUM 语言 $L$ 是所有满足以下条件的对 $(S, t)$ 的集合：

\[ L = \{(S, t) \mid \text{存在 } S \text{ 的一个子集 } S' \subseteq S \text{，使得子集 } S' \text{ 中的元素之和等于 } t \} \]

证：

（1）定义证书

如果语言L的一个实例(S, t)属于该语言，那么必定存在一个证书C。

对于该问题，最直接的证书C就是那个和为t的子集S'。

如果SUBSET-SUM的答案是“是”，那么我们总能找到这个证书。

我们假定C的长度是K，S的长度是N。

（2）验证机验证

我们需要用验证机来验证证书是有效的。

首先，证书中的数字都来自于原始集合。我们可以对证书中的数字注意检查，确保他们都在原始集合S中。

接着，我们计算证书中的和，然后和目标t对比。如果证书中的和和目标t一样，那么证书就是真是的。

（3）判断验证速度属于多项式时间

我们来看验证机验证的过程，其过程如下：

在S中查找C中的数字，对于大小为N的S，查找一个数字最坏情况是N，因此查找证书C的最坏情况就是CN，这是一个多项式时间。
把C中的数字加起来需要用掉K的时间，这是一个多项式时间。
比较C中数字的和和t，这只需要一次比较，是一个多项式时间。如果和是t，那么验证机就接受C；否则拒绝C。

可见，所有验证步骤都可以在多项式时间内完成。因此对于原问题，我们总能找到一个证书C，并在多项式时间内验证。根据NP的定义，语言L有一个多项式时间验证机，因此L属于NP。

（英文版）

Prove:

If some subsets of S sums to exactly t, then we can always find a certificate C, and this certificate is a subset of S and the sum of certificate's elements is t. We can define the subset S' as this certificate.

We need build a verifier to verify this certificate.

First, the numbers in the certificate should come from S. We can check the number in C to judge if they are from S.

Then, we can add the numbers in S', to compare with t. If the sum is the same as t, then SUBSET-SUM is true.

We can define a verifier V, to determine whether we can accept or reject C.

The verification steps are:

(1) Check the number in C to judge if they are from S. There are K numbers in S' and N numbers in S. Then check each number cost N in worst case, so total time we cost is O(KN)

(2) Add the numbers in C, cost O(K)

(3) Compare the sum of C and t, this cost O(1). If the sum is t, then verifier V accept C, otherwise V reject C.

We can see that all verification steps are polynomial time. Therefore, we can verify in polynomial time. So for SUBSET-SUM problem, we can always find a certificate C, and verify in polynomial time. According to definition of NP, SUBSET-SUM now has a verifier can verify in polynomial time, so SUBSET-SUM is in NP.

2COLOR问题

证明2COLOR属于NP

2COLOR就是说可以给一个图进行上色，上色颜色有两种，并且可以实现所有相邻的两个顶点颜色都不同。

\[ \text{2COLOR} = \{G \mid G \text{ has a proper 2-vertex coloring}\} \]

Prove:

For an input graph G, if G has a proper 2-vertex coloring, then there exists a certificate C implementing such a coloring.

We need build a verifier V to verify this certificate C. The verifier V receives the graph G and the certificate C as input.

The verification steps are:

(1) Check all colors in the graph is one of the two valid colors. This cost O(V) time.

(2) Check all vertexes if they have a neighbor has same color. If there exist a situation that two neighbor vertexes have same color, the verifier V immediately reject C. This cost O(V+E) time if we use BFS to traverse the graph, or O(E) time if we can traverse the set of edges.

(3) If there is no rejection happens, after verification, the verifier V accept C.

We can see that all verification steps are polynomial time. Therefore for 2COLOR problem, if the input graph G has a proper 2-coloring, the certificate C can be verified in polynomial time. Hence, by the definition of NP, 2COLOR is in NP.

3COLOR问题

证明3COLOR属于NP

3COLOR就是说可以给一个图进行上色，上色颜色有三种，并且可以实现所有相邻的两个顶点颜色都不同。

\[ \text{3COLOR} = \{G \mid G \text{ has a proper 3-vertex coloring}\} \]

Prove:

For an input graph G, if G has a proper 3-vertex coloring, then there exists a certificate C implementing such a coloring.

We need build a verifier V to verify this certificate C. The verifier V receives the graph G and the certificate C as input.

The verification steps are:

(1) Check all colors in the graph is one of the three valid colors. This cost O(V) time.

(2) Check all vertexes if they have a neighbor has same color. If there exist a situation that two neighbor vertexes have same color, the verifier V immediately reject C. This cost O(V+E) time if we use BFS to traverse the graph, or O(E) time if we can traverse the set of edges.

(3) If there is no rejection happens, after verification, the verifier V accept C.

We can see that all verification steps are polynomial time. Therefore for 3COLOR problem, if the input graph G has a proper 3-coloring, the certificate C can be verified in polynomial time. Hence, by the definition of NP, 3COLOR is in NP.

7.5 coNP

co就是Complement（补集）。coNP 是所有 补集（Complement） 属于 NP 的语言集合，$coNP$ 的定义：

\[ coNP = \{ L \mid \overline{L} \in NP \} \]

即一个语言 $L$ 属于 $coNP$，当且仅当它的补集 $\overline{L}$ 属于 $NP$。

证明：if $P = NP$ then $NP = coNP$

证明上述结论：

根据集合论定义，要证明 $A = B$，需要证明 $A \subseteq B$ 且 $B \subseteq A$。我们将利用假设 $P = NP$，以及确定性多项式时间类 ($P$) 的一个关键性质：如果你能在多项式时间内确定性地解决一个问题，你也一定能在多项式时间内解决它的反面问题（即补集）。

假设 (Assumption): $P = NP$。

第一部分：证明 $NP \subseteq coNP$****

任取一个语言 $L \in NP$。
根据假设 $P = NP$，既然 $L \in NP$，那么 $L \in P$ 。
根据引理（$P$ 对补集封闭——这个关键性质很好证明，对于确定性图灵机，只需要把“接受”变成“拒绝”，“拒绝”变成“接受”，就可以证明P对补集封闭），因为 $L \in P$，所以 $\overline{L} \in P$ 。
再次利用假设 $P = NP$，因为 $\overline{L} \in P$，所以 $\overline{L} \in NP$ 。
根据 $coNP$ 的定义，既然 $L$ 的补集 $\overline{L} \in NP$，那么 $L \in coNP$ 。
综上，对于任意 $L \in NP$ 都有 $L \in coNP$，因此 $NP \subseteq coNP$ 。

第二部分：证明 $coNP \subseteq NP$****

任取一个语言 $L \in coNP$。
根据 $coNP$ 的定义，这意味着 $\overline{L} \in NP$ 。
根据假设 $P = NP$，既然 $\overline{L} \in NP$，那么 $\overline{L} \in P$ 。
根据引理（$P$ 对补集封闭），因为 $\overline{L} \in P$，所以其补集 $\overline{\overline{L}}$（即 $L$）也属于 $P$，即 $L \in P$ 。
再次利用假设 $P = NP$，因为 $L \in P$，所以 $L \in NP$ 。
综上，对于任意 $L \in coNP$ 都有 $L \in NP$，因此 $coNP \subseteq NP$ 。

结论 (Conclusion):

既然我们证明了 $NP \subseteq coNP$ 且 $coNP \subseteq NP$，那么可以得出结论：

若 $P = NP$，则 $NP = coNP$。

Ch.8 NP完全

NP-Complete（NP完全）是NP的子集，是NP中最难的那一类问题。

1763842819509

8.1 可满足性问题

20 世纪 70 年代，斯蒂芬·库克 (Stephen Cook) 和列昂尼德·列文 (Leonid Levin)发现了 NP 中某些问题的复杂性与整个复杂度类 NP 的复杂性相关联：如果任何一个 NP 完全问题 存在多项式时间算法，那么所有 NP 问题 都有多项式时间算法（即 $P=NP$）。

换言之，在理论方面，研究 $P \ne NP$ 的人可以把精力集中在寻找一个 NP 完全问题的非多项式时间证明上。在实践方面，NP 完全性可以防止人们浪费时间去寻找不存在的多项式时间算法。

第一个被证明是NP完全问题的问题是可满足性问题（SAT）：

\[ SAT = \{\langle \phi \rangle \mid \phi \text{ 是可满足的布尔公式}\} \]

定理： $SAT \in P$，当且仅当 $P=NP$。

该定理说明，如果 SAT 问题可以在多项式时间内求解，那么所有 NP 问题都可以在多项式时间内求解，意味着 $P$ 等于 $NP$。反之亦然。

8.2 多项式时间可归约

一个函数 $f: \Sigma^* \to \Sigma^*$ 称为 多项式时间可计算函数 ，如果存在一个多项式时间图灵机 $M$，使得在任何输入 $w \in \Sigma^*$ 上，$M$ 停机时，带子上恰好是 $f(w)$。这个函数 $f$ 的计算过程可以在多项式时间内完成。这是“有效”转换的基础。

语言 $A$ 称为多项式时间映射可归约到语言 $B$（简称多项式时间可归约），记为 $A \le_p B$，如果存在一个多项式时间可计算函数 $f: \Sigma^* \to \Sigma^*$，使得对于每一个 $w$，有：

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

函数 *$f$ 称为 $A$ 到 $B$ 的 多项式时间归约 (polynomial time reduction) 。$f$ 是一个从集合 $A$ 的输入域到集合 $B$ 的输入域的映射。要判断一个串 $w$ 是否属于 $A$，只需要多项式时间计算出 $f(w)$，然后判断 $f(w)$ 是否属于 $B$* 即可。

$A \le_p B$ 意味着：问题 $A$ 不会比问题 $B$ 更难解决 （在多项式时间复杂度意义下）。如果 $B$ 有一个高效（多项式时间）的解法，那么 $A$ 也可以通过归约到 $B$ 得到高效的解法。

定理: 若 $A \le_p B$ 且 $B \in \mathbf{P}$，则 $A \in \mathbf{P}$。

$\mathbf{P}$ 是多项式时间可解的语言的集合。

证明该定理的思路:

设 $M$ 是判定 $B$ 的多项式时间算法（图灵机）。
设 $f$ 是 $A$ 到 $B$ 的多项式时间归约函数。
构造判定 $A$ 的算法 $N$ 如下：
输入 $w$。
计算 $f(w)$* （在多项式时间内完成，因为 *$f$ 是多项式时间可计算函数）。
在输入 $f(w)$ 上运行 $M$* （在多项式时间内完成，因为 *$M$ 是多项式时间算法）。
输出 $M$ 的结果。
算法 $N$ 的总运行时间是计算 $f(w)$ 的多项式时间与运行 $M$ 的多项式时间的合成，仍然是 多项式时间 。
因此 $A$ 是多项式时间可解的，即 $A \in \mathbf{P}$。

为了引入后续重要的归约例子，课本介绍了布尔公式的一些概念：

文字 (literal): 一个布尔变量（如 $x$）或其非（如 $\bar{x}$）。
子句 (clause): 由 $\lor$（或）连接的若干个文字。
合取范式 (conjunctive normal form, cnf): 由 $\land$（且）连接的若干个子句。
3cnf 公式: 要求公式中 所有子句都恰好有三个文字 。
例: $(x_1 \lor \bar{x}_2 \lor x_3) \land (\bar{x}_1 \lor x_4 \lor \bar{x}_5)$
3SAT 问题: 给定一个 3cnf 公式 $\phi$，问是否存在一个布尔赋值使得 $\phi$ 可满足（即 $\phi$ 的值为 True）。后面课本上给出了一个关于3SAT多项式时间可归约到CLIQUE的证明。

8.3 NP-hard

如果一个问题被归类为 NP-Hard，意味着它至少和世界上所有“很难解决但容易验证”的问题（NP 类问题）一样难。

这里要注意的是，NP-Hard不是NP的子集。NP-Hard中的一部分是NP，一部分则比NP还要难（连验证答案都无法在多项式时间内完成）。

如果世界上所有的 NP 问题（NxN数独、哈密顿、俄罗斯方块...），都可以“转化”（Reduction）为问题 X。那么问题 X 就是 NP-Hard 。如果一个 NP-Hard 问题能被 快速解决（在多项式时间内） ，那么所有的 NP 问题都能被 快速解决（在多项式时间内） 。

换句话说，如果有一个NP-Hard问题能在多项式时间内解决，那么我们就证明了 P = NP。

8.4 NP完全

一个语言 $B$ 被称为 NP 完全 （NP-complete），如果它满足下面两个条件：

$B$ 属于 NP ：
这意味着对于任何给定的输入，如果它是 $B$ 的一个“是”实例，那么存在一个多项式时间内可验证的“证书”（或称“解”），来证明这个输入确实属于 $B$。
NP 中的每个语言 $A$ 都多项式时间可归约到 $B$ ($\text{A} \le_p \text{B}$):
这意味着 $B$ 是 NP 集合中最“难”的问题之一。如果我们可以高效地（多项式时间内）解决 $B$ 问题，那么我们就可以高效地解决 NP 中所有其他的问题。
多项式时间可归约性 ($\le_p$)：存在一个多项式时间可计算的函数 $f$，使得对于所有输入 $w$，$\text{w} \in \text{A} \iff f(w) \in \text{B}$。

定理 P = NP 问题与 NP 完全：

若上述的 $B$ 是 NP 完全的，且 $B \in \mathbf{P}$，则 $\mathbf{P} = \mathbf{NP}$。

P 类 （Polynomial time）：可以在多项式时间内解决（求解）的问题集合。
NP 完全的语言 $B$ 是 NP 中最难的问题。
如果最难的 $B$ 竟然可以在多项式时间内解决（即 $B \in \mathbf{P}$），那么根据定义 7.27 的第 2 条（所有 NP 语言都可以归约到 $B$），NP 中的所有问题就都可以在多项式时间内被解决。
因此，这证明了P 类和 NP 类是同一个集合，即 $\mathbf{P} = \mathbf{NP}$。

定理 NP 完全性的传递性：

若上述的 $B$ 是 NP 完全的，且 $B \le_p C$，$C$ 属于 NP ，则 $C$ 是 NP 完全的。

证明思路： 要证明 $C$ 是 NP 完全的，需要证明两个条件：

$C$ 属于 NP ：这是定理的已知条件。
NP 中的每个语言都可归约到 $C$**** ：
已知 $B$ 是 NP 完全的，所以 NP 中的任何语言 $A$ 都可以多项式时间归约到 $B$ ($A \le_p B$)。
已知 $B$ 可以多项式时间归约到 $C$ ($B \le_p C$)。
多项式时间可归约性具有复合性（或传递性） ：如果 $A \le_p B$ 且 $B \le_p C$，那么 $A \le_p C$。
因此，NP 中的每个语言 $A$ 都可以多项式时间归约到 $C$。

这说明，只要一个语言 $C$ 是 NP 语言，并且 比一个已知的 NP 完全问题更难（或者和它一样难） ，那么 $C$ 也是 NP 完全的。这是证明新问题是 NP 完全问题的 主要方法 。

简单总结：

NP 完全问题就是 NP 中最难的那一群问题。
如果任何一个 NP 完全问题被证明可以在多项式时间解决，那么所有 NP 问题都可以在多项式时间解决（$\mathbf{P} = \mathbf{NP}$）。
证明一个新问题 $C$ 是 NP 完全的，通常是通过证明某个已知的 NP 完全问题可以多项式时间归约到 $C$ (同时 $C$ 属于 NP )。

8.5 库克列文定理

库克-莱文定理 （Cook–Levin theorem）是计算复杂性理论中一块基石，它回答了“NP 完全”这个概念是否真的存在的问题，并为后续发现其他 NP 完全问题奠定了基础。

8.6 已知的NP完全

3-SAT

3-Coloring

Vertex Cover

定理： VERTEX-COVER是NP完全的。

HAMPATH

定理1： HAMPATH是NP完全的。

定理2： UHAMPATH是NP完全的。

CLIQUE

Subset Sum

定理： SUBSET-SUM是NP完全的。

8.7 证明是NP完全

NP-Complete是NP和NP-Hard的交集，因此要证明一个问题是NP-Complete，就必须同时证明：

该问题属于NP
该问题属于NP-Hard

证明属于NP可以参见笔记中证明属于NP的部分，一般用多项式时间验证的Certificate来解。

证明NP-Hard较为困难。一个问题属于NP-Hard，说明该问题至少和现在所有的NP问题一样难。我们不可能直接对所有的NP问题进行证明，而是通过多项式时间归约的方法，将一个已知是NP-Complete的问题A，归约到我们要证明的问题L中。其核心逻辑是证明$A \le_p L$ （已知问题 $\le$ 你的问题），即如果你能有效地解决 $L$，你就能利用这个解法有效地解决 $A$。因为 $A$ 已经很难了，所以 $L$ 必然也一样难（或更难）。

这里要注意，一定是把一个已知难题归约到我们要证明的问题中。

归约的具体流程（4个子步骤）：

选择已知问题 $A$：通常选择结构上与 $L$ 相似的问题。常用的已知 NPC 问题包括：（参考上一小节内容）
3-SAT （逻辑满足问题，万能起点）
CLIQUE （团问题，常用于图论问题）
Vertex Cover （顶点覆盖）
3-Coloring （3着色问题）
Hamiltonian Cycle （哈密顿回路）
构造变换函数 $f$：你需要设计一个算法，将 $A$ 的任意一个输入实例 $I_A$，转换成 $L$ 的一个输入实例 $I_L$。 $$ I_L = f(I_A) $$
证明变换是多项式时间的：证明构造 $I_L$ 的过程不需要花费指数级时间。
证明等价性（充要条件）：这是证明的核心。你需要证明：
充分性 ($\Rightarrow$)：如果 $I_A$ 是“Yes实例”（有解），那么转换后的 $I_L$ 也是“Yes实例”。
必要性 ($\Leftarrow$)：如果 $I_L$ 是“Yes实例”（有解），那么原实例 $I_A$ 也是“Yes实例”。（通常通过逆否命题证明：如果 $I_A$ 无解，则 $I_L$ 也无解）。

Double Clique

$DOUBLE-CLIQUE$ 问题：

\[ DOUBLE-CLIQUE = \{(G, k) \mid G \text{ has at least 2 cliques, each of size greater than or equal to } k\} \]

简单来说，即给定一个图 $G$ 和一个整数 $k$，如果这个图里能找到至少两个大小不小于 $k$ 的团（Clique），那么这个输入就属于该语言。

团 (Clique) ：图中的一个顶点子集，其中任意两个顶点之间都有边相连（即完全子图）。

特性	图灵可识别 (Turing-recognizable)	图灵可判定 (Turing-decidable)
对于\(w \in L\)(在语言中)	必须停机并接受	必须停机并接受
对于\(w \notin L\)(不在语言中)	可以停机并拒绝，也可以永不停机	必须停机并拒绝
是否总停机？	不一定	是，总会停机

M 在 w 上的行为	属于 ATM 吗?	属于 HALTTM 吗?
\(M\)接受\(w\)	是	是(因为接受也是一种停机)
\(M\)拒绝\(w\)	否	是(因为拒绝也是一种停机)
\(M\)在\(w\) 上无限循环	否	否

计算理论：自动机理论

Ch.0 离散数学基础

0.1 逻辑与证明方法

归纳法

构造法

反证法

0.2 数学概念和术语

Ch.1 正则语言

1.1 字符串和语言

1.2 有限状态机

1.3 形式化定义

1.4 正则运算

闭包性质

并运算 Union

连接运算 Concatenation

星号运算 Star

1.5 正则表达式

1.6 泵引理

Ch.2 上下文无关文法

2.1 CFG与CFL

2.2 形式化定义

2.3 下推自动机

2.4 泵引理

2.4 DCFL

2.5 封闭性

Ch.3 图灵机

3.1 图灵机

3.2 形式化定义

3.3 丘奇-图灵论题

Ch.4 可判定性

4.1 可识别的语言

4.2 可判定的语言

4.3 对角化方法

Ch.5 可归约性

5.1 证明不可判定

5.2 证明停机问题不可判定

5.3 证明L17不可判定

5.4 证明M17不可判定且不可识别

5.5 证明T不可判定

5.6 证明奇图灵机不可识别

5.7 可计算函数

Ch.6 P类

6.1 时间复杂性

6.2 多项式时间

6.3 P类问题

6.4 多项式等价性

6.5 证明是P

PATH问题

RELPRIME问题

2COLOR问题

Ch.7 NP类

7.1 NP类问题

7.2 HAMPATH问题

7.3 COMPOSITES问题

7.4 证明是NP

SUBSET-SUM问题

2COLOR问题

3COLOR问题

7.5 coNP

Ch.8 NP完全

8.1 可满足性问题

8.2 多项式时间可归约

8.3 NP-hard

8.4 NP完全

8.5 库克列文定理

8.6 已知的NP完全

3-SAT

3-Coloring

Vertex Cover

HAMPATH

CLIQUE

Subset Sum

8.7 证明是NP完全

Double Clique

Dominating Set

评论 #