From 8e29158b170e0b92fc6b48a283107f64af00898c Mon Sep 17 00:00:00 2001
From: pw384 <pw384@pku.edu.cn>
Date: Sat, 9 Mar 2019 01:10:38 +0800
Subject: [PATCH] Create cc-basic.md
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

开坑：计算理论基础
---
 docs/misc/cc-basic.md | 70 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 70 insertions(+)
 create mode 100644 docs/misc/cc-basic.md

diff --git a/docs/misc/cc-basic.md b/docs/misc/cc-basic.md
new file mode 100644
index 00000000..5224b313
--- /dev/null
+++ b/docs/misc/cc-basic.md
@@ -0,0 +1,70 @@
+本部分将介绍基础的计算理论的知识。
+
+## 语言
+
+设 $\sigma$ 是一个字符集。 $\sigma$ 上的所有的串构成集合 $\sigma^*$ 。称字母表 $\sigma$ 上的语言 $L$ 就是 $\sigma^*$ 的一个子集。非形式化来说，语言就是字符串的集合。
+
+## 图灵机、可判定性与丘奇-图灵论题
+
+如果你已经知道图灵机在计算复杂性上和普通计算机多项式地等价的话，那么可以跳过这一段。
+
+### 图灵机
+
+非形式化地说，图灵机包含一个有限状态机、一条两端无限长的纸带和一个指针。图灵机的每一步操作包括一次状态转移和一次指针移动。采用何种操作的依据是当前的状态以及指针指向的字符。一般情况下输入位于图灵机的纸带上，而指针初始位置指向输入字符串的开头。形式化地，一个图灵机是七元组 $M=(Q,\sigma, \gamma, \delta, q_0, B, F)$ ，其中
+
+1. $Q$ 是状态机的状态集合。
+2. $\sigma$ 是字符集。
+3. $\gamma$ 是带符号的集合，且 $\sigma$ 是 $\gamma$ 的真子集。一般取 $\gamma = \sigma \cup \{ B \}$ ，$B$ 的含义后述。
+4. $\delta(q, X)$ 是转移函数。其中参数 $q\in Q$ 是有限状态机的一个状态，$X\in \gamma$ 是带符号。转移函数的输出可能为一个三元组 $(q', X', D)$ ，也可能直接使图灵机停机，其中 $q'\in Q$ 为下一状态， $X'\in\gamma$ 为向当前指针指向的格子中填入的字符， $D$ 是写下新字符以后指针移动的方向， 一般取 $D$ 为向左一格、向右一格、不动这三个选择。
+5. $q_0$ 是状态机的初始状态。
+6. $B$ 是空格符号。这一符号不在字符集中，但是在带符号之中。开始时，除了输入串外，纸带上每个格子都是 $B$ 。
+7. $F$ 是状态机的终结状态构成的集合。
+
+称图灵机 $M$ 接受一个字符串 $s$ ，如果 $M$ 最终达到接受态并停机，记 $M(s) = 1$ 。称图灵机 $M$ 拒绝一个字符串 $s$ ，如果 $M$ 已停机但未停在接受态，记 $M(s) = 0$ 。注意，对于某些串，图灵机可能永不停机，也就是说 $\{s:M(s)=1\}\cup\{s:M(s)=0\}$ 有可能不是全集。记所有 $M$ 接受的串构成的语言为 $L(M)$ 。称图灵机 $M$ 判定语言 $L$ ，如果 $L=L(M)$ ，且对于任意 $s\notin L$ ，都有 $M(s) = 0$ 。
+
+### 可判定性
+
+一个语言称为递归可枚举的，如果存在一个图灵机接受它。一个语言 $L$ 被称为可判定的（递归的），如果存在一个图灵机判定它。注意递归的语言都是递归可枚举的语言，反之不然（由于历史原因而产生这个可能导致误解的命名）。
+
+（挖坑）
+
+### 丘奇-图灵论题
+
+（挖坑）
+
+### 非确定性图灵机
+
+（大坑）
+
+## 复杂度类 P、NP与coNP
+
+（挖坑）
+
+## Karp归约、Cook-Levin定理与NP完全性
+
+（大坑）
+
+## 经典问题所在的复杂性类
+
+（大大坑）
+
+## 其它复杂度类
+
+### 随机复杂性类
+
+（大坑）
+
+### 空间复杂性类
+
+（大坑）
+
+## 你知道吗？
+
+下面是一些关于复杂性理论的有意思的结果（随时补充）。
+
+1. 时间层次定理：$\mathbf{DTIME}(o(\frac{f(n)}{\log f(n)}))$ 是 $\mathbf{DTIME}(f(n))$ 的真子集。一个直接的结论就是 $\mathbf{P}\neq\mathbf{EXP}$ 。
+2. 如果 $\mathbf{P}\neq\mathbf{NP}$ ，那么存在一个NP问题，它既不在P中，也不是NP完全的。（Ladner定理）
+3. 如果图同构问题的判定版本是NP完全的，那么PH（多项式层级）会坍塌，而人们不相信PH会坍塌。
+4. MAX-3SAT问题（尽可能满足数量多的子句）不存在 $\frac{7}{8}+\varepsilon$ 近似比的多项式时间算法，除非 $\mathbf{P}=\mathbf{NP}$ 。这个定理是1997年才被证明的。（Hastad的PCP定理）
+5. 虽然人们不知道是否有 $\mathbf{P}\neq\mathbf{NP}$ ，但人们知道 $\mathbf{PSPACE}=\mathbf{NPSPACE}$ 。（Savitch定理）
+6. 不存在多项式时间的算法统计一个二部图完美匹配的数量，除非 $\mathbf{P}=\mathbf{NP}$ 。这是一个判定版本（二部图有没有完美匹配？）与计数版本（有多少完美匹配？）计算复杂性相差悬殊的例子。
-- 
2.11.0