复杂度

常见

• 双对数：$\mathrm{O}(\log \log n)$
• 多项式对数 polylog：$\mathrm{O}\left({\log }^{c}n\right)$
• 拟线性：$\mathrm{O}\left(n{\log }^{c}n\right)$

IMPORTANT

表示渐近性质的符号 $\mathrm{O}$ 是大写希腊字母 Omicron，而不是英文字母 $O$。

$T(n)$ 与 $\mathrm{O}(n)$

• 时间指的是状态转移的次数；
• $T(n)$ 是一个函数，表示输入规模为 $n$ 情况下，算法的最差运行时间；
• $S(n)$ 是一个函数，表示输入规模为 $n$ 情况下，算法在工作带上最多使用 $S(n)$ 个格子。
• $\mathrm{TIME}(T(n))$ 表示存在一个图灵机在 $\mathrm{O}(T(n))$ 时间内判定 $L$。
• $\mathrm{DTIME}(T(n))$ 表示存在一个多带图灵机在 $\mathrm{O}(T(n))$ 时间内判定 $L$。
• $\mathrm{NTIME}(T(n))$ 表示存在一个 NTM 在 $\mathrm{O}(T(n))$ 时间内判定 $L$。
• $\mathrm{SPACE}(S(n))$ 表示存在一个图灵机在 $\mathrm{O}(S(n))$ 空间内判定 $L$。
  $\mathrm{DTIME}(\mathrm{S}(\mathrm{n}))\subseteq \mathrm{SPACE}(\mathrm{S}(\mathrm{n}))\subseteq \mathrm{NSPACE}(S(n))\subseteq \mathrm{DTIME}\left(2^{\mathrm{O}(S(n))}\right)$
• $\mathrm{O}(n)$ 是一类函数，表示运行时间的渐近上界为 $kn$ 的所有函数构成的集合。
• $\Omega (n)$ 表示渐近下界，$\Theta (n)$ 当且仅当 $\mathrm{O}(n)$ 和 $\Omega (n)$。
• 对应的小写字母表示无论常数取多少都满足条件，例如 $\omega (n)$ 表示对任意 $k$ 都有 $n$ 充分大时 $f(n)>kn$。

图灵停机问题

$$L_{halt}:=\{(\alpha ,x):M_{\alpha }在输入x停止\}$$

Time-constructible Functions 时间可构函数

这是函数的一个性质。

• 定义 1: 存在图灵机在输入 $1^n$ 之后恰好执行 $f(n)$ 步后停机；
• 定义 2: 存在图灵机在输入 $1^n$ 之后在 $\mathrm{O}(f(n))$ 时间内输出 $f(n)$ 的二进制。

空间可构造函数

存在图灵机在输入 $1^n$ 之后在 $\mathrm{O}(f(n))$ 空间内输出 $f(n)$ 的二进制。

不同类型的语言

1. $P:={\bigcup }_{c⩾1}\mathrm{DTIME}(n^c)$
2. NP: 可以在多项式时间内验证，或者由 NTM 在多项式时间内解决，即 $NP={\bigcup }_{c⩾1}\mathrm{NTIME}(n^c)$
3. NP-Hard: 任何一个 NP 语言可以归约到它
4. NP-Complete: NP-Hard 的 NP
5. NP-Immediate: NP 但不是 NP-Hard

TIP

证明一个问题是 NP-Complete 的方法 先证明 NP，再将一个 NP-Hard 问题归约到这个问题上。

常见的 NP 问题

• SAT
• PCP
• INDSET
• CLIQUE
• HAMPATH / HAMCYCLE
• TSP
• VERTEXCOVER
• MAXCUT
• dHAMPATH（有向图上的哈密顿路径）是 NP 完全问题

常见的 NP-Immediate 问题

• 图同构
• 大整数分解

归约

定义

存在一个图灵机，对输入 $x$ 满足 $M(x)\in L_2$ 当且仅当 $x\in L_1$。

映射归约

符号 $L_1{⩽}_m{L}_2$

称 $L_1$ 可以映射归约到 $L_2$，若有一个可计算函数 $\phi$ 满足 $x\in L_1$ 当且仅当 $\phi (x)\in L_2$。

图灵归约

符号 $L_1{⩽}_T{L}_2$

称 $L_1$ 可以图灵归约到 $L_2$，若任意一个拥有对 $L_2$ 有神谕的神谕图灵机都可以判定 $L_1$。

NOTE

换句话说，就是如果已经可以判断是否 $x\in L_2$（即便不是用图灵机来判定），那么也可以用同样的方法来判断是否 $x\in L_1$。

部分性质：

• 若 $L_1{⩽}_m{L}_2$，则 $L_1{⩽}_T{L}_2$。
• $L{⩽}_T\overline{L}$。

Karp 归约（多项式时间映射归约）

符号 $L{⩽}_{p}K$

$L$ 可以 Karp 归约到 $K$ 的定义： 存在多项式时间的 $TM$ 可以把集合 $L$ 变换到 $K$，即

$$x\in L⟺M(x)\in K,\forall x\in \{0,1{\}}^{\ast }.$$

Cook 归约（多项式时间图灵归约）

符号 $L{⩽}_{k}K$

$L$ 可以 Cook 归约到 $K$ 的定义：存在对 $K$ 有神谕的神谕图灵机在多项式时间内判定 $L$。

$L$ 在 Karp 归约下是 NP 难当且仅当它在 Cook 归约下是 NP 难。

NOTE

Cook 归约允许在神谕图灵机上运行多项式时间，这意味着它可以至多多项式次查询神谕。而 Karp 归约相当于是一个有一个只能查询一次神谕的神谕图灵机。

可计算性

常见的不可判定语言

• $L_{halt}:=\{(\alpha ,x):M_{\alpha }对于输入x停机\}$。由于 $L_{flip}:=\{\alpha :M_{\alpha }不接收\alpha \}$ 是不可判定的，而且 $L_{flip}⩽L_{halt}$。所以 $L_{halt}$ 是不可判定的。
• $L_{flip}:=\{\alpha :\alpha \notin L(M_{\alpha })\}$ 不可判定。
• $L_{accept}:=\{(\alpha ,x):M_{\alpha }接收x\}$ 不可判定。
• $L_{empty}:=\{⟨M⟩:L(M)=\varnothing \}$ 不可判定。
• $L_{regular}:=\{⟨M⟩:L(M)是正则语言\}$ 不可判定。
• $L_{equal}:=\{(⟨M_1⟩,⟨M_2⟩):L(M_1)=L(M_2)\}$ 不可判定。
• $L_{Dio}:=\{⟨P(x_1,\cdots ,x_n)⟩:P(x_1,\cdots ,x_n)=0有解\}$ 不可判定。

语言的性质

设 $M$ 和 $N$ 是任意两个被图灵机识别的语言。如果 $P$ 满足“若 $L(M)=L(N)$ 则 $⟨M⟩\in P\iff ⟨N⟩\in P$ ”，则称 $P$ 是一个性质。

如果存在 $T{M}_{\alpha }$ 使得 $\alpha \in P$ 且存在 $T{M}_{\beta }$ 使得 $\beta \notin P$，则称 $P$ 是非平凡性质。

性质也是语言。

Rice 定理

非平凡性质 $P$ 是不可判定的。

证明方法：证明 $L_{accept}{⩽}_{m}P$。

反证，假设 $P$ 由图灵机 $M_P$ 判定。

根据输入 $(\alpha ,x)$ 构造一个 $M^{\prime }$：$M^{\prime }$ 先模拟 $M_{\alpha }(x)$，如果 $M_{\alpha }$ 接收了 $x$，则 $M^{\prime }$ 接着模拟任何一个 $M_{\beta }$ 的行为，其中 $\beta \in P$；否则模拟一个 $M_{\gamma }$ 的行为，其中 $\gamma \notin P$。这样，$⟨M^{\prime }⟩\in P\iff (\alpha ,x)\in L_{accept}$。

由于 $L_{accept}$ 是不可判定的，所以 $P$ 也是不可判定的。

NOTE

在这个证明过程中，$(\alpha ,x)$ 是构造 $M^{\prime }$ 用到的参数，但不是 $M^{\prime }$ 接受的输入。

还可以把其他常见的不可判定问题归约到 $P$ 上，例如 $L_{halt}$。

时间分层定理

若 $f$ 和 $g$ 是时间可构造函数，满足 $f(n)\log f(n)=o(g(n))$，则 $\mathrm{DTIME}(f(n))⊊\mathrm{DTIME}(g(n))$。

空间分层定理

若 $f$ 和 $g$ 是空间可构造函数，满足 $f(n)=o(g(n))$，则 $\mathrm{SPACE}(f(n))⊊\mathrm{SPACE}(g(n))$。