Computational Complexity NP-Completeness
$\textbf{NP}-$Completeness
判定一个问题是否是NP问题，需要证据与验证，即：
当存在一个多项式$p: \textbf{N}\to \textbf{N}$和一个$\text{P}-\text{time}$图灵机$\mathbb{M}$，使得对于语言$L$以及$x \in \{0,1\} ^*$：
$$
x \in L \space\text{iff}\space \exists u\in \{0,1\} ^{p(|x|)},\mathbb{M}(x,u)=1
$$
则称$L$是一个$\textbf{NP}$问题，并称这个图灵机$\mathbb{M}$为一个验证器。
上面的定理中，$u$就称为能够证明$L$是一个$\textbf{NP}$问题的“证据”。该定理说明，若某个问题是$\textbf{NP}$问题，则一定存在一个确定图灵机$\mathbb{M}$，它能通过不超过多项式长度的证据判定该问题在$\textbf{NP}$中。
事实上，$u$就是非确定图灵机$\mathbb{N}$正确判断$x$的一条路径。因为要验证的是$\textbf{NP}$，所以要求路径长度（即$u$的长度）为多项式。
Karp Reduction
Karp Reduction即为多项式时间归约，其定义为：
若存在一个多项式时间的可计算函数$r:\{0,1\} ^* \to \{0,1\} ^*$，使得对所有的$x \in \{0,1\} ^*$，
$$
x \in L \space \text{iff} \space r(x) \in L '
$$
则称$L$可多项式归约到$L'$，记为$L \le _K L'$。
多项式归约也具有传递性。
- 如果$L \in \text{NP}$且$L \le _K L'$，则称$L'$是$\textbf{NP}$难的；
- 若$L' \in \textbf{NP}$，则称$L '$是$\textbf{NP}$完全的。
若P = NP，则EXP = NEXP。底层相等，上层也相等。
Propositional Logic：命题逻辑
命题公式，即一个逻辑公式，是由真假值（0/1）、命题变量和逻辑操作子通过归纳构造的。一个命题变量$x$是一个布尔量，也称作“字（Literal）”，其否定形式为$\overline{x}$。逻辑运算符包括$\lor$（或、析取），$\land$（与、合取）。若干个“字”的析取称语句，若干个“字”的合取称单项式。
- 合取范式（Conjunctive Normal Form，CNF）：若干语句的合取，记作$\lor _{i}(\land _j v _{ij})$。
- 析取范式（Disjunctive Normal Form，DNF）：若干单向式的析取，记作$\land _{i}(\lor _j v _{ij})$。
对于某一公式（合取或析取，记作$\phi$），若存在$v _{ij}$的某种真值指派，使得$\phi$为真，则称该公式是可满足的（Satisfiable）。对于所有可满足的合取范式组成的集合$\textbf{SAT}$，存在如下定理：
$$
\textbf{SAT} \in \textbf{NP}
$$
$k\textbf{SAT}$是指每个语句只含有$k$个字的合取范式。对于$k\textbf{SAT}$，有如下结论：
- $2\textbf{SAT}\in \textbf{P}$
- $\textbf{SAT}\le _K 3\textbf{SAT}$
结论2表明，$k$（$k \ge 3$）$\textbf{SAT}$可由$3\textbf{SAT}$表示。
布尔函数$f:\{0,1\} ^\ell \to \{0,1\}$将$\ell$长的$01$串映射为一个布尔值，它可以被表示为一个合取范式，且该合取范式的大小不会超过$\ell 2 ^\ell$。
Cook-Levin Theorem
定理：$\textbf{SAT}$是$\textbf{NP}$完全的。该定理证明如下：
由于$\textbf{SAT}\in \textbf{NP}$，故要证上述定理成立，只需要证明$\forall L \in \textbf{NP}$，$L \le _K \textbf{SAT}$，即证明$x \in L$当且仅当$\phi(x) \in \textbf{SAT}$，又$x \in L$等价于$\exists u \in \{0,1\} ^{ ^{p (|x|)}},\mathbb{M}(x,u)=1$，所以即证明：
$$
\phi(x) \in \textbf{SAT}\space \text{iff}\space \exists u \in \{0,1\} ^{ ^{p (|x|)}},\mathbb{M}(x,u)=1
$$
要证明上式，即证明图灵机的计算过程可以一个合取范式表示。由于任何多带的图灵机都可以单带图灵机在多项式的代价下模拟，所以此处只考虑一条带子。则对于图灵机的整个计算过程，其产生的所有格局中的每一个格子、带头是否在该格子、当前的状态可用$1+\log \Gamma +\log Q$个比特编码，记其长度为$\ell$。对于格局$C _{i+1}$和其上一个格局$C _{i}$，$C _{i + 1}$的每一个格子的值只会受到其正上方、左上方、右上方三个$C _{i}$格子的影响。所以，对于$C _i \to C _{i+1}$每一个格子的转移函数可以表示为$f:\{0,1\} ^{3\ell}\to \{0,1\} ^\ell$，其等价于$f:\{0,1\} ^{4\ell} \to \{0,1\}$，转换为合取范式，其大小为$4\ell 2 ^{4 \ell}$，由于$\ell$为常量，所以前式为常数。前后格局所有格子的转换都可用上式表示，记该转移函数为$C$。终止格局数为多项式，格局的大小也是多项式，所以$x \to \phi(x)$的转换是多项式的。证毕。
此外，计算$C _{ij}$的空间是对数的，只需要记录$i$和$j$即可。
性质
- 库克-莱文归约是个莱文归约（Levin Reduction），即使得$\phi(x)$成立的一组真值指派$u$就是使得$\mathbb{M}(x,u)=1$的证据$u$。
- 归约是对数空间的。
判定问题有多项式时间算法，则相应的计算问题也有。
判定（Decision）和计算（Search）问题在是否有高效算法上是等价的，即若我们能在多项式时间内判定某个问题，我们就能在多项式时间内计算其对应的计算问题。
Karp Theorem
Karp证明了21个NP完全问题，如$\textbf{THEOREM}$——能否在多项式的公式长度的行内证明某公式是NP完全的。
Berman-Hartmanis Conjecture
猜测（Conjecture）：任何的NP完全问题都是多项式同构的，即只有一个NP完全问题。若该猜测为真，则$\textbf{P} \neq \textbf{NP}$。
多项式同构：$A \le _K ^1 B$表存在从$A$到$B$的单射Karp归约，若$A \le _K ^1 B \le _K ^1 A$，则称$A$和$B$是多项式同构的，即$A \simeq _P B$
对于集合$S \subseteq \{0,1\} ^* $，若$S$内部长度不超过$n$的串有指数个，即$|S ^{\le n}|= 2 ^{n ^{O(1)}}$，则称该集合是稠密的；反之若只有多项式个，即$|S ^{\le n}|= {n ^{O(1)}}$，则称该集合是稀疏的。$\textbf{SAT}$是稠密的，而$\textbf{P}$类问题是稀疏的，稠密集合不可能和稀疏集合同构，因为大的映射小的或小的映射大的不可能是单射的，所以$\textbf{SAT} \ne \textbf{P}$。
Ladner Theorem
定理：若$\textbf{NP} \neq \textbf{P}$，则存在介于$\textbf{P}$和$\textbf{NP}$之间的语言。
证明的基本思路：从$\textbf{SAT}$中排除一些元素，但不至于退化为$2\textbf{SAT}$，则新的语言就介于$\textbf{NP}$和$\textbf{P}$之间。记该新语言为$\textbf{SAT} _H$。
$$
\textbf{SAT} _H(x)=
\begin{cases}
1, &x \in \textbf{SAT} _H\\
0, &x \notin \textbf{SAT} _H
\end{cases}
$$
$$
H(n)=
\begin{cases}
i, &\text{对}|x|\le \log n\text{可在}i |x| ^i\text{时间内判定}\textbf{SAT} _H(x)\text{的最小图灵机下标}\\
\log \log n, &\text{otherwise}
\end{cases}
$$
$H(n)$是单调不减的，其时间复杂度为：
$$
T(n)=(\log\log n)2 ^{\log n}(c\cdot C\log C+ 2 ^{\log n}+ T(\log n)+...)
$$
- $\log\log n$是因为我们要枚举所有的$i < \log \log n$以找到下标最小的图灵机；
- $2 ^{\log n}$是因为对于每一次枚举，我们都要验证所有长度小于$\log n$的序列，共有指数个；
- $c\cdot C\log C$是用通用图灵机模拟$\mathbb{M} _i(x)$计算$i |x| ^i$步的时间；
- $2 ^{\log n}$是暴力计算$\textbf{SAT} _H(x)$的时间；
- 后面这两项需要是因为我们要将模拟结果与$textbf{SAT} _H(x)$的真实值进行比较；
- $T(\log n)$是因为在计算$\textbf{SAT} _H(x)$时还要计算$H(|\psi|)$，而$\psi$的长度为$\log n$。
- 可以算得$T(n) = o(n ^3)$。
$H(n)$的性质
- 如果$H(n)$是有限的，由于$H(n)$是非递减的，$H(n)$最终会收敛到$i$，即$\exists n \ge N$，使$H(n)=i$恒成立。于是$\exists$图灵机$\mathbb{M}_i$，它在多项式时间$i|x| ^i$内判定$\textbf{SAT} _H$。
- $\textbf{SAT} _H \in \textbf{P}\space \space \text{iff} \space \space H(n)$是有限的。右到左即性质1，左到右：
设图灵机$\mathbb{M} _i$在$c n ^c$内判定$\textbf{SAT}_H$。由于图灵机编码的任意性，我们可以取$i \ge c$，而$H(n)$输出的是图灵机的最小编码，所以一定有$H(n) \le i$。
两个方向的证明
推论1：如果$\textbf{P} \ne \textbf{NP}$，则$\textbf{SAT} _H \notin \textbf{P}$。
因为若$\textbf{SAT} _H \in \textbf{P}$，则由$\textbf{SAT} _H$的定义，$\textbf{SAT}\le _K \textbf{SAT} _H$。
推论2：如果$\textbf{P} \ne \textbf{NP}$，则$\textbf{SAT} _H$不是NP完全的。
不懂
Baker-Gill-Solovay Theorem
定理：存在$A$使得$\textbf{P} ^A = \textbf{NP} ^A$，也存在$B$$\textbf{P} ^B \ne \textbf{NP} ^B$
对前项的证明：
$$
\textbf{PSPACE}=\textbf{P} ^{\textbf{PSPACE}} \subset \textbf{NP} ^{\textbf{PSPACE}} = \textbf{PSPACE}
$$
于是$\textbf{P} ^{\textbf{PSPACE}} = \textbf{NP} ^{\textbf{PSPACE}}$。该项说明，若$A$的表达能力足够强，则$\textbf{P} ^A$会与$\textbf{NP} ^A$的表达能力相当。对后项的证明：
令$B _0 = \{\}$，$n _0 = 0$，并使得$B _{i + 1}$和$B _i$存在如下递推关系：
- 让图灵机$\mathbb{M} _i ^{B _i}$在问题$1 ^{n _i + 1}$上运行$2 ^{n _{i+1}-1}$步；
- 若不停机，则令$B _{i+1} = B _i$；
- 若接受，则令$B _{i+1} = B _i$；
- 若拒绝，则令$B _{i+1} = B _i \cup \{s\}$，其中$s$是长度为$n _{i+1}$的字符串，且在图灵机运行的过程中没有被用于问子程序$B _i$（因为图灵机只运行$2 ^{n _{i+1}-1}$步，不能枚举完所有的长度为$n _{i+1}$的串）。
此外，还规定$n _{i+1}$是严格递增的，且必须大于所有的会被作为图灵机$\mathbb{M} _0 ^{B _0}(x _1)...\mathbb{M} _{i-1} ^{b _{i-1}}(x _i)$的输入串$x$。
最终，$B$就定义为$B = \bigcup _{i \in \textbf{N}} B _i$。再定义$U _B = \{1 ^n | B \text{包含长度为}n\text{的串}\}$，即，若$B$包含长度为$n$的串，则$U _B$包含长度为$n$的全1串。对于任意的全1串，我们可证$U _B \in \textbf{NP} ^B,U _B \notin \textbf{P} ^B$。左边易证，我们只需枚举所有长度为$n$的字符串并询问$B$即可，对于右边：
假设存在$\mathbb{M} _i ^B$在多项式时间判定$U _B$，则，如果：
- $\mathbb{M} _i ^B(1 ^{n+1})=0$，那么$B$中不包含长度为$n + 1$的字符串，而长度为$n + 1$的字符串只能在$B _{i+1} = B _i \cup \{s\}$被加入到$B _{i+1}$中，所以$B _{i+1}$中不包含长度为$n+1$的串。
由此我们可以推出矛盾：
- $\mathbb{M} _i ^{B _i}(1 ^{n+1})=1\to B _{i+1} = B _i \to\mathbb{M} _i ^{B _{i+1}}(1 ^{n+1})=1 \to \mathbb{M} _i ^B(1 ^{n+1})=1$
证毕。
Oracle Turing Machine：神谕图灵机
神谕图灵机$\mathbb{M} ^?$是一种特殊的图灵机，它有一条额外的读写带和新的三种状态$q _{text{query}}, q _{\text{yes}}, q _{\text{no}}$。
这条额外的带子实际上就是“子程序”。“$?$”可被替换为一个实际的问题/语言，如$B$。
神谕图灵机通过进入$q _{\text{query}}$状态来询问某个字符串$b$是否属于$B$，这相当于一次“子程序”调用。如果$b \in B$，则进入$q _\text{yes}$状态；否则，进入$q _{\text{no}}$状态
子程序调用只算作一次计算！
对神谕图灵机的编码是对机器的编码，与神谕无关。
Cook Reduction
如果存在一个多项式时间复杂度的神谕图灵机$\mathbb{M} ^?$，使得语言$L$可以被图灵机$\mathbb{M} ^{L'}$判定，则称语言$L$可以Cook归约到$L'$，记作$L \le _C L'$。
Lowness
如果$\textbf{A} ^{\textbf{B}}=\textbf{A}$，则称复杂性类$\textbf{B}$相对于复杂性类$\textbf{A}$是低的。
换句话说，$\textbf{A}$调用$\textbf{B}$并不能增强自身判定问题的能力，这说明相对于$\textbf{A}$，$\textbf{B}$解决的问题是更简单的问题。