TCS

computability

1. function and encoding

TCS 研究的终极目标就是如何计算函数. 对此有两个子目标: 函数的可计算性 (Computability, 是否可被 Turing Machine 计算) 和复杂性 (Complexity, 需要多少时空资源)

研究 encoding 的意义在于把任意的集合 (图, 矩阵, 多项式等数学对象) 映射到字符串. 后面的研究都基于 \(\set{0,1}^*\)

prefix-free encoding 的意义是不用逗号即可实时解码, 例如 Universal Turing Machine 中接受 \(\langle M,x\rangle\), 需要界定 \(M\) 在哪里结束, \(x\) 在哪里开始

可以得出两个重要概念:

1. encodable \(\Leftrightarrow\) countable
2. boolean functions are uncountable

在后面会发现 boolean functions 定义的 language 都是 uncoutable, 而所有的 automaton 都是 encodable, 所以 countable, 所以一定会存在 uncomputable functions

2. NAND-circuit and NAND-program

用来计算 finite functions \(f: \set{0,1}^n\to\set{0,1}^m\)

3. DFA, NFA, regular language and regular expressions

用来计算 infinite functions \(f: \set{0,1}^*\to\set{0,1}^*\)

特别地, 由于任意 infinite function 与 boolean function \(bf: \set{0,1}^*\to\set{0,1}\) 等价, 所以只考虑 boolean function 即可

对于一个 language \(L\subseteq \set{0,1}^*\), 与 boolean function \(\set{0,1}^*\to\set{0,1}\) 等价

所以 language 定义为 \(A_f\set{x\in\set{0,1}^*|f(x)=1}\)

DFA 是 chomsky hierarchy 中最简单的计算模型, 同时等价于 NFA

ragular language 即定义为 DFA 可判定的 language, 是最简单的语言; 通常使用是否可被 NFA 判定来判断 language 是否 regular

4. PDA, CFG, context-free language

5. TM, NAND-TM, NAND-RAM and Turing Complete

6. uncomputable functions, reduction and Rice's Theorem

要证明存在 uncomputable functions 可以通过 language uncountable, TM countable 来说明, 也可以构造 \(F^*\)

uncomputable functions: \(F^*,HALT,HALTONZERO,ZEROFUNC\)

7. Recursion Theorem and Godel's Incompleteness Theorem

两个不可计算的有趣定理

7.1. Recursion Theorem

Lemma: Self-Printing TM

证明自己可以打印自己

之后可以用相同思想证明 Recursion Theorem

一些使用 Recursion Theorem 证明的例子:

1. \(HALT\) is uncomputable

2. \(MINI\) is uncomputable

3. Fix Point Theorem

7.2. Godel's incomplete theorem

\(T\) 是所有 true statements 的集合

如果 proof system \(V\) complete, 那么 \(\forall x\in T, \exists t, V(x,t)=1\)

theorem of proof system

for some \(T\), there's no complete proof system \(V\)

假设存在 complete proof system \(V\)

可以归约到 \(HALTONZERO\)

run parallelly
    1.
    run M on 0;
    return 1;
    2.
    x = "M does not halt on 0"; // statement in T
    t = 0; // proof
    for(t, increase in length){
        if(V(x, t) == 1) return 0;
    }

如果 \(M\) 在 \(0\) 上停机, 那么第一条停机, 第二条不停机, 此时检测到第一条停机立即返回 \(1\)

如果 \(M\) 不停机, 那么根据假设, 第二条一定会找到一个证明, 那么第二条停机, 所以返回 \(0\)

所以 \(HALTONZERO\) 可计算, 完成归约

quantified integer system

\(\star\) chomsky hierarchy

TYPE 3: 正则语言 regular language

\(L=\set{a^n|n\geq 0}\)

TYPE 2: 上下文无关语言 context-free language

\(L=\set{a^nb^n|n\geq 0}\)

TYPE 1: 上下文有关语言 context-sensitive language

\(L=\set{a^nb^nc^n|n\geq 0}\)

TYPE 0: 递归可枚举语言

~~编译原理中有这个内容~~

complexity

1. \(P\) and \(TIME(T(n))\)

TIME hierarchy theorem

2. \(P_{\setminus poly}\) and \(SIZE(T(n))\)

\(P_{\setminus poly}\) 是一个神奇的类, 包含了不可计算的函数

目前 \(P_{\setminus poly}\) 与 \(NP\) 的关系仍然未知

\(P_{\setminus poly}\) 包含了不可判定问题，但主流观点认为它偏偏包不住 \(NP\) 中的 Hard 问题

1. 核心猜想：\(NP \nsubseteq P/poly\)

这是目前学界最主流的猜想。意思是：NP-完全问题（如 SAT）不存在多项式大小的电路族。

• 如果 \(NP \subseteq P/poly\)，意味着虽然我们可能找不到一个通用的多项式时间算法来解决 SAT（即 \(P \neq NP\)），但对于任意固定的输入长度 \(n\)，都存在一个只有多项式大小的逻辑电路能瞬间算出 SAT 的结果。
• 大多数学家认为这是不可能的。

2. 关键定理：Karp-Lipton 定理

如果 \(NP\) 真的包含在 \(P/poly\) 中，会发生什么？Karp-Lipton 定理 (1980) 给出了后果：

定理：如果 \(NP \subseteq P/poly\)，那么多项式层级（Polynomial Hierarchy, PH）将塌缩到第二层，即 \(PH = \Sigma_2^p\)。

解释： * 一般认为多项式层级（PH）是无限的，或者至少不会塌缩到那么低的层级。 * 因此，Karp-Lipton 定理通过归谬法暗示了 \(NP\) 很可能不包含在 \(P/poly\) 中。

3. 反向包含：\(P/poly \nsubseteq NP\)

这一点是可以严格证明的：\(P/poly\) 绝对不是 \(NP\) 的子集。

• 理由：\(NP\) 中的所有语言都是可判定的（Decidable），即一定存在图灵机能解决它们。
• 但是，\(P/poly\) 包含不可判定（Undecidable）的语言。
  • 例子：考虑“一元停机问题”。定义语言 \(L\)：如果第 \(n\) 个图灵机在空输入上停机，则 \(1^n \in L\)；否则 \(1^n \notin L\)。
  • 这是一个不可判定问题。但是对于任意长度 \(n\)，答案是固定的（要么全是1，要么不是）。电路可以直接“硬编码”这个 Yes/No 的答案。因此 \(L \in P/poly\)。
  • 因为 \(NP\) 不包含不可判定问题，所以 \(P/poly \not\subseteq NP\)。

4. 与 P vs NP 的关系

研究 \(NP\) 和 \(P/poly\) 的关系是解决 \(P\) vs \(NP\) 问题的一条重要路径：

1. 更强的猜想： 证明 \(NP \nsubseteq P/poly\) 比证明 \(P \neq NP\) 要难得多（是一个更强的结论）。

   • 因为 \(P \subseteq P/poly\)，如果你证明了 \(NP\) 甚至连 \(P/poly\) 都不属于，那它自然也不属于 \(P\)。
   • 即：\(NP \nsubseteq P/poly \implies P \neq NP\)。

2. 目前的现状：

   • 我们知道 \(NP \subseteq EXP\)。
   • 我们不知道 \(NP\) 是否属于 \(SUBEXP\)（亚指数时间）。
   • 关于电路复杂度，目前最好的下界证明非常弱。我们甚至无法证明 \(NP\) 中的问题需要大于 \(3n\) 或 \(5n\) 大小的电路（对于一般电路而言）。要证明需要“超多项式大小”的电路，路还非常长。

总结

关系方向	结论	理由/定理
\(P/poly \subseteq NP\)?	False (不成立)	\(P/poly\) 包含不可判定语言，而 \(NP\) 仅包含可判定语言。
\(NP \subseteq P/poly\)?	Conjectured False (猜想不成立)	Karp-Lipton 定理：如果成立，则 PH 塌缩，这被认为是不太可能的。
交集	Non-empty (非空)	两者都包含 \(P\)。

3. \(NP\) and \(NPC\)

主要研究 3SAT

4. BPP

研究 \(BPP\), \(P\), \(P_{\setminus poly}\) 之间的关系, 尝试证明 \(P?=NP\)

\(\star\) attempts for proving \(P=NP\)

1. \(P\subseteq NP\subseteq EXP\), 其中必有一个 \(\subsetneq\)
2. if \(P=BPP\), then \(P=NP\)

important theorem

encodable \(\Leftrightarrow\) countable

\(O(\frac{m2^n}n)\) circuit

\(\underline{\text{Sketch}}\)

分块, 利用小的 k, 花费 \(2^k\) 来构造出 \(f:\set{0,1}^k\to \set{0,1}\), 从而得到所有 \(2^{2^k}\) 函数, 之后复用这些函数, 用 \(2^{n-k}\) 个门引到最终输出, 得到 \(F:\set{0,1}^k\to \set{0,1}^{2^{n-k}}\)

之后 LOOKUP, 电路复杂度 \(O(2^{n-k})\)

取 \(2^k=n-2\log_2 n\)

总的 \(O(2^k\cdot 2^{2^{k}}+2^{n-k})=O(\frac{2^n} n)\)

证明紧性:

encoding \(s\log s\), 取 \(s=\frac{2^n}{cn}\)

\(\underline{\text{Proof}}\)

\(f:\set{0,1}^* \to \set{0,1}^* \Leftrightarrow bf:\set{0,1}^* \to \set{0,1}\)

DFA \(\Leftrightarrow\) NFA

\(\underline{\text{Sketch}}\)

把 NFA 对应每一层的 \(2^n\) 种状态用 \(2^n\) 个 DFA 节点表示

转移到每个状态需要同时遍历所有 \(e\) 转移到的状态

\(\underline{\text{Proof}}\)

Pumping Theorem

\(\underline{\text{Sketch}}\)

一个 language 对应的自动机的状态是有限的, 对于长度大于状态数的输入, 总存在一个环

\(\underline{\text{Proof}}\)

PDA \(\Leftrightarrow\) CFG

\(\underline{\text{Sketch}}\)

有了 CFG 构造 PDA, 就把 CFG 的转移规则重写成 PDA 的转移规则, 在栈里构造 non-deterministic 串, 与输入匹配

有了 PDA 构造 CFG, 先构造 simple PDA, 即 \(|f|=1\), 每次只能 push/pop 一个字符

用 simple PDA 构造 CFG:

simple PDA = \(\set{K,S,\Delta,\set{f}}\)

构造 \(V=\set{0,1}\cup \set{A_{pq}: p,q\in K}\), \(S=A_{sf}\), 目标是 \(A_{pq}\Rightarrow w\text{ iff }w\in\set{u\in\set{0,1}^*|(p,u,e)\to(q,e,e)}\)

此时 \(A_{sf}\) 作为起始字符, 能够通过 \(R\) 转移到所有 simple PDA 接受的 \(w\) 上

\[R=\set{A_{pp}\to e|p\in K}\]

\[\cup\set{A_{pq}\to A_{pr}A_{rq}|p,q,r\in K}\]

\[\cup\set{A_{pq}\to aA_{rs}b|\exists X, ((p,a,e),(r,X))\in \Delta \wedge ((s,b,X),(q,e))\in \Delta}\]

\(\underline{\text{Proof}}\)

HALT is uncomputable

general proof

\(\underline{\text{Sketch}}\)

将 \(F^*\) 归约到 \(HALT\)

\(F^{*}\) 不能用图灵机计算的一个原因是图灵机不一定停机, 构造出的 \(M_F\) 不一定有输出

所以假设 \(HALT\) 可计算, 判定输入的图灵机是否停机, 不停机就返回

这样 \(F^{*}\) 可以被 \(M_F\) 计算, 得到矛盾

\(\underline{\text{Proof}}\)

using Recursion Theorem

Recursion Theorem 不需要归约了

像 \(F^*\) 一样构造一个与自己矛盾的图灵机即可

M = on input x
  obtain <M>
  compute HALT(<M>, x)
  if HALT(<M>, x) == 1:
    loop
  else:
    halt

所以 M halts on x iff HALT(M, x) = 0

Rice's Theorem

将 \(HALT\) 归约到 property \(P\)

假设 \(M_{INF}\) 永不停机

不妨设 \(P(M_{INF})=0\), 否则考虑 \(1-P\)

\(\exists M_{yes}\text{ s.t. } P(M_{yes})=1\)

定义:

N = on input y
  run M on x
  run M_yes on y and return M_yes(y)

则 HALT(M,x) = 0 if P(N) = 0, HALT(M,x) = 1 if P(N) = 1

所以 if \(P\) computable, then \(HALT\) computable

即 reduction from \(HALT\) to \(P\)

\(\square\)

Recursion Theorem

\(\underline{\text{Sketch}}\)

我想自己打印自己, 但是一句一句打印会出现循环打印下一句话的情况

所以可以拆成两个 \(A,B\), 互相打印

但是如果 \(A\) 打印了 \(<B>\), \(B\) 也直接打印了 \(<A>\), 就又嵌套了

所以可以显式在 \(A\) 打印 \(<B>\), \(B\) 隐式打印 \(<A>\)

具体地, 构造函数 \(q\):

q(w) = <M_w>
M_w = on input x
  erase input
  write w on the tape

B = on input w
  write q(w) on the tape
  swap with w

A = on input y
  erase input
  write <B> on the tape

先运行 \(A\), 纸带上是 \(<B>\)

之后运行 \(B(<B>)\), 写上了 \(q(<B>)=<A>\), 并与 \(<B>\) 交换

因此完成了自己打印自己

之后证明 Recursion Theorem, 只需要构造 \(A,B,T\) 即可

\(\underline{\text{Proof}}\)

HALT

见上

MINIMAL

证明 MINI uncomputable

\(\underline{\text{Sketch}}\)

对于 M, 获取 <M>, 循环找 s, 使得 MINI(s) = 1 并且 |<s>|>|<M>|

之后 return s(x)

那么 s 和 M 功能等价, 但 MINI(s) = 0, 矛盾

\(\underline{\text{Proof}}\)

Fixed Point Theorem

\(\underline{\text{Sketch}}\)

对于 F, 计算 t(<F>), 令 <M> = t(<F>)

之后 return M(x)

\(\underline{\text{Proof}}\)

Godel's Incompleteness Theorem

\(\underline{\text{Sketch}}\)

归约到 HALTONZERO

并行执行两个语句:

HALTONZERO = on input M parallelly
1. run M on 0
2. x = "M does not halt on 0"
  for t:
    run V on (x,t)
    if V(x,t) == 1:
      return 0

必有一个停机, 一个不停机

则 M halts -> first halts -> HALTONZERO(M) = 1

M does not halt -> second halts -> HALTONZERO(M) = 0

所以 HALTONZERO computable, 矛盾

\(\underline{\text{Proof}}\)

TIME Hierarchy Theorem

定义 bounded HALT problem:

\(HALT_T(P,x)=1,|P|\leq \log\log|x|\quad \text{and}\quad P \text{ halts on } x \leq 100T(|P|+|x|) \text{ steps}\)

\(HALT_T(P,x)=0 \text{ otherwise}\)

\(\underline{\text{Sketch}}\)

Proof 1:

if |P| > loglog|x|
  return 0
compute T0 = T(|P|+|x|)
simulate P on x in 100 * T0 steps // universal TM: U(P, x) simulate P on x in a * |P|^b * 100 * T0 steps
if halt:
  return 1
else 
  return 0

total:

\[O(|P|^bT_0)\]

\[\leq O(T_0\cdot \log\log^b(|P|+|x|))\]

\[\leq O(T(|P|+|x|)\cdot \log\log^b(|P|+|x|))\]

\[\leq O(T(|P|+|x|)\cdot \log(|P|+|x|))\]

Proof 2:

构造 \(Q^*\)

Q* on input z:
  if z not in form P1^m, |P| < 0.1loglogm:
    return 0
  run HALT_T on z // O(|P|+|z|) = O(2|P|+m)
  if halts:
    loop
  else:
    halt

对于 \(Q^*(P1^m)\):

1. loops, if \(|P|<0.1\log\log m\quad \text{and}\quad P \text{ halts on }P1^m\leq 100T(2|P|+m)\text{ steps}\)
2. halts, otherwise

令 \(P=Q^*, m=2^{2^{1000|Q^*|}}\), 考察 \(Q^*(Q^*1^m)\)

1. first, loops but halts
2. second, halts within \(2T(2|P|+m)\) steps; 但是这种情况说明应该是第一种情况

所以得到两条矛盾

\(\underline{\text{Proof}}\)

\(TIME(T(n))\subseteq SIZE(T(n)^3)\)

\(\underline{\text{Sketch}}\)

1. 对于循环, copy k 次即可, 循环次数为 T(n), 所以乘以一个 T(n)

2. 对于 MODEANDJUMP, 扫一个来回纸带, 定位到对应的 index 即可, 加上一个 2T(n)

最后 \(O((T(n)+2T(n))*T(n))=O(T(n)^2)\)

\(\underline{\text{Proof}}\)

\(P \subsetneq P_{\setminus poly}\)

\(\underline{\text{Sketch}}\)

往证: \(\exists f\in P_{\setminus poly}\), \(f\) is uncomputable

考虑 unary halting problem

\(\underline{\text{Proof}}\)

\(P\subseteq NP\subseteq EXP\)

\(\underline{\text{Sketch}}\)

P\subset NP: 用 \(V(x,t)\) 直接模拟 P 对应的 \(M(x)\) 即可

NP\subset EXP: NP 的certificate |t|\leq |x|^a

所以在 2^{|x|^a} 的时间里枚举所有 t 即可

\(\underline{\text{Proof}}\)

Cook Levin Theorem

定义 NANDSAT:

NAND-CIRC program, \(n\) inputs, \(1\) output, \(Q(t)=1\)?

\(\underline{\text{Sketch}}\)

F\leq_p NANDSAT\leq_p SAT\leq_p 3SAT

1. SAT\leq_p 3SAT

多拆少补

\[(x_1\vee x_2)\wedge(x_1\vee x_2\vee x_3\vee x_4)\]

\[\to(x_1\vee x_2\vee y)\wedge (x_1\vee x_2\vee \bar y)\]

\[\wedge (x_1\vee x_2\vee y)\wedge (x_3\vee x_4\vee \bar y)\]

1. NANDSAT\leq_p SAT

\(\vee\) 和 \(\wedge\) 可以表示 NAND

1. F\leq_p NANDSAT

解决 \(F\in NP\) 等于找一个 \(t\), \(|t|\leq |x|^a\), \(V(x,t)=1\)

对于 V 展开循环:

input length \(\leq |x|+|t|\leq 2|x|^a\)

running time \(\leq (|x|^{a})^b\leq 2^b|x|^{ab}\)

变成一个 NAND-CIRC Q, poly(2^b|x|^{ab}, |V|)

Q(x,t)=V(x,t)

对于每个固定的 \(x\) 相当于计算是否 \(Q'(t)=Q(x,t)=V(x,t)=1\), \(t\in \set{0,1}^{|x|^a}\)

\(\underline{\text{Proof}}\)

\(3SAT\) is \(NPC\)

• Corollary: \(3SAT\) in \(P\) iff \(P=NP\)

Amplification Lemma

\(\underline{\text{Sketch}}\)

多运行几次求 majority

\(\underline{\text{Proof}}\)

\(P\subset BPP\subset EXP\)

1. \(P\subset BPP\)

RNAND-TM 本身就是 NAND-TM + RAND(), 自然包含 \(P\)

1. \(BPP\subset EXP\)

和 NP 一样枚举

Adleman's Theorem

\(BPP \subsetneq P_{\setminus poly}\)

Lemma

\(F\in BPP\) iff \(G\in P\) s.t. \(\forall x\in \set{0,1}^*\)

\(Q\) 是对应 \(F\) 的 RNAND-TM program

\[Pr[Q(x)=F(x)]=Pr[G(xr)=F(x)]\geq 2/3\]

\(r\) 是伪随机数列

\(\underline{\text{Sketch}}\)

利用振幅引理

\[Pr_{r\sim \set{0,1}^{a|x|^b}}[G(xr)=F(x)]\geq 2/3\to 1-\frac{0.1}{2^n}\]

所以固定 \(|x|=n\):

\[Pr_{r\sim \set{0,1}^{a|x|^b}}[G(xr)=F(x),\forall |x|=n]\geq 1-2^n\cdot(\frac{0.1}{2^n})=0.9\]

所以 \(\forall n\), \(\exists r\), \(|r|=a|x|^b\), s.t. \(G(xr)=F(x), \forall |x|=n\)

\(\underline{\text{Proof}}\)

\(P=BPP\) if Optimal Pseudorandom Generator exists

定义 Pseudorandom Generator:

$$$$

optimal: m\to l

所以可以将所有随机数列降维成 \(\log n\) 级别的, 再枚举所有随机数列, 这样枚举的复杂度就是 \(P\) 而不是 \(EXP\) 的, 所以 \(P=BPP\)

equivalent

countable \(\Leftrightarrow\) encodable

DFA \(\Leftrightarrow\) NFA

• DFA defines regular language

  所以得到 NFA \(\Leftrightarrow\) regular language

NFA \(\Leftrightarrow\) regular expression

• 由上, 得到 NFA \(\Leftrightarrow\) regualr expression 即可得到 regular language \(\Leftrightarrow\) regular expression

PDA \(\Leftrightarrow\) CFG

\(\underline{\text{Proof.} }\)

\(\Leftarrow\)

证明 PDA \(\Leftrightarrow\) simple PDA \(\Leftrightarrow\) CFG

• PDA defines context-free language

TM \(\Leftrightarrow\) NAND-TM circuit = NAND-CIRC circuit + arrays + loops

TM defines computable functions

NAND-TM circuit \(\Leftrightarrow\) NAND-RAM circuit

RNAND-TM program = NAND-TM + RAND()

goal

我们需要研究计算模型, 用来计算函数

常见的计算模型有 circuit, automaton, language, grammar 等

计算能力层级对应表

层级 (Hierarchy)	语言 (Language)	语法 (Grammar)	自动机 (Automaton)	电路 (Circuit) 等价	编程语言 (Programming Language) 等价
Type-0 (图灵完备)	递归可枚举语言 (Recursively Enumerable Languages)	无限制语法 (Unrestricted Grammars)	图灵机 (Turing Machine)	多项式时间均匀的电路族 (P-uniform circuit families)	任何通用编程语言 (例如 Python, C++, Java)
Type-1 (上下文相关)	上下文相关语言 (Context-Sensitive Languages)	上下文相关语法 (Context-Sensitive Grammars)	线性有界自动机 (Linear Bounded Automaton, LBA)	没有直接的、标准的等价物	没有直接的、标准的等价物
Type-2 (上下文无关)	上下文无关语言 (Context-Free Languages)	上下文无关语法 (Context-Free Grammars, CFG)	非确定性下推自动机 (Nondeterministic Pushdown Automaton, NPDA)	语法解析电路 (Parsing circuits), 与并行计算复杂性类相关	编程语言的语法定义 (BNF 范式), 解析器 (Parsers)
Type-3 (正则)	正则语言 (Regular Languages)	正则语法 (Regular Grammars)	有限状态机 (Finite Automaton, FA/FSA/DFA/NFA)	时序逻辑电路 (Sequential Logic Circuits)	正则表达式 (Regular Expressions)

对每个层级的详细解释

Type-0: 递归可枚举语言 (图灵完备)

这是计算能力的最强层级，描述了所有“可计算”或“可判定”的问题。 - 语言 (Language): 递归可枚举语言。指的是存在一个图灵机，当一个字符串属于该语言时，该图灵机最终会停机并接受它。如果字符串不属于该语言，图灵机可能停机并拒绝，也可能永不停机。 - 语法 (Grammar): 无限制语法。其产生式 α → β 对 α 和 β 的形式没有任何限制（除了 α 不能为空）。 - 自动机 (Automaton): 图灵机 (Turing Machine)。这是该层级的标准模型，拥有一个无限长的带子作为内存，可以模拟任何算法。所有变种，如多带图灵机、非确定性图灵机，在计算能力上都是等价的。 - 电路 (Circuit): 多项式时间均匀的电路族。单个电路只能处理固定长度的输入，但一个“电路族”（每个输入长度 n 对应一个电路）可以识别一个语言。如果存在一个图灵机能在 poly(n) 时间内生成第 n 个电路，那么这个电路族就和多项式时间图灵机在能力上等价。因为任何逻辑门都可以用 NAND 门实现，所以 NAND 门电路族也具备这种能力。 - 编程语言 (Programming Language): 任何通用编程语言，如 Python、C++、Java、Lisp 等。它们之所以是图灵完备的，是因为它们具备两个关键特性：1) 通过循环 (while/for) 或递归实现重复操作；2) 拥有理论上无限制的内存（例如，可以动态申请内存）。这些特性使其能够模拟图灵机的任何计算。

Type-1: 上下文相关语言

这个层级的能力介于图灵完备和上下文无关之间。 - 语言 (Language): 上下文相关语言。 - 语法 (Grammar): 上下文相关语法。其产生式形如 αAβ → αγβ，意味着 A 只有在上下文 α 和 β 中才能被替换为 γ。一个关键要求是，替换后的字符串长度不能缩短。 - 自动机 (Automaton): 线性有界自动机 (Linear Bounded Automaton, LBA)。它是一种特殊的图灵机，其读写带的长度被限制为输入长度的常数倍。它不能使用无限的带子空间。 - 电路与编程语言: 在这个层级上，没有直接或标准的等价模型。虽然可以构造一个只使用其输入大小的线性空间的程序来模拟 LBA，但这并不是一种通用的编程语言范式。同样，也没有一个被广泛接受的电路类别与 LBA 精确对应。这个层级主要用于理论分析。

Type-2: 上下文无关语言

这个层级对于编程语言的语法分析至关重要。 - 语言 (Language): 上下文无关语言。例如，所有括号正确匹配的表达式。 - 语法 (Grammar): 上下文无关语法 (CFG)。其产生式形如 A → γ，其中 A 是一个非终结符。替换 A 时不依赖其上下文，这是它与 Type-1 的核心区别。巴科斯范式 (BNF) 就是描述 CFG 的常用方式。 - 自动机 (Automaton): 非确定性下推自动机 (Nondeterministic Pushdown Automaton, NPDA)。它比有限状态机多了一个栈作为内存。这个栈赋予了它“记忆”能力，例如可以记住左括号的数量以便与右括号匹配。值得注意的是，确定性下推自动机 (DPDA) 的能力比 NPDA 弱。 - 电路 (Circuit): 没有像 Type-3 那样直接的对应关系，但上下文无关语言的识别问题与某些并行计算复杂性类（如 LOGCFL）和特定结构的布尔电路紧密相关。 - 编程语言 (Programming Language): 编程语言的语法结构。几乎所有现代编程语言的语法都是（或大部分是）上下文无关的。解析器 (Parser)，如 YACC 或 ANTLR 生成的解析器，就是识别这种结构的程序。它们将代码字符串转换为抽象语法树 (AST)。

Type-3: 正则语言

这是最基础、能力最受限的层级，但应用极其广泛。 - 语言 (Language): 正则语言。例如，电子邮件地址的格式、所有由偶数个 "a" 组成的字符串等。 - 语法 (Grammar): 正则语法。所有产生式都形如 A → aB (右线性) 或 A → Ba (左线性)，其中 A 和 B 是非终结符，a 是终结符。 - 自动机 (Automaton): 有限状态机 (Finite Automaton, FA)。它没有额外的内存，只有有限个状态。它可以是确定性的 (DFA) 或非确定性的 (NFA)，两者在计算能力上是等价的。 - 电路 (Circuit): 时序逻辑电路 (Sequential Logic Circuits)。任何有限状态机都可以被直接实现为一个硬件电路，其中状态由触发器 (Flip-flops) 存储，状态转换逻辑由组合逻辑门（如 AND, OR, NOT, NAND）实现。 - 编程语言 (Programming Language): 正则表达式 (Regular Expressions)。在几乎所有编程语言和文本编辑器中，用于字符串搜索、匹配和替换的正则表达式引擎，其理论基础就是有限状态机。词法分析器 (Lexer) 也是一个典型的应用，它将源代码分解成一个个的 token (如关键字、标识符、运算符)。

前期介绍的所有计算模型及其相关理论, 都是为了得到 (目前) 最强大的计算模型: 图灵机, 以及得到 Church Turing thesis, 即图灵机可计算的函数为 computable functions

interesting facts

about \(\log n\)

• 在理论计算机和算法中, 复杂度最好是 O(N), 即与数据规模呈线性关系; 常见的很多算法多是 NlogN 的, 其他还有 loglogN, \sqrt{\logN} 的算法; 同时在 TCS 中的复杂度理论中, 定理通常证明原复杂度类对应的复杂度 T(n) 变成 T(n)logn 后, 复杂度类一定会拓展, 即存在一个函数可以被 T(n)logn 计算但不能被 T(n) 计算. logn 有什么特殊意义? 它是否是简单复杂度函数(即不包含嵌套 loglogn)中最小的一个增量?

这个问题问得非常“理论计算机味”，而且你已经站在门内了。我们慢慢拆开这只看似普通、实则爱惹事的 log n。

先给一个总判断，再解释原因： log n 之所以反复出现，不是因为它神秘，而是因为它是“信息论上最小的、还能改变世界的代价”。 它几乎是你能加在复杂度上、仍然足以让复杂度类发生严格变化的最小非平凡增量。

---

一、log n 的本质：信息与选择的最小单位

在理论计算机里，log n 有一个极其朴素、但杀伤力很强的解释：

log n ≈ 用二进制表示 n 所需要的位数。

这意味着三件事：

1. 区分 n 种可能性至少要 log n 比特 这是信息论下界，不依赖模型、不依赖语言、不依赖你喜不喜欢。

2. 任何“全局决策”都绕不开 log n 比如：

3. 二分搜索：每一步减少一半不确定性

4. 排序的比较下界：n! 的信息量是 n log n

5. 地址、索引、指针、本质都在付 log n 的账单

6. log n 是“非局部”的最小成本 常数是局部的；log n 开始，你已经在和输入规模的整体结构打交道了。

---

二、为什么复杂度分离定理里偏偏是 T(n) vs T(n)·log n？

你提到的，其实是 时间层级定理（Time Hierarchy Theorem） 的核心形态之一：

对足够可构造的 T(n)， DTIME(T(n)) ⊊ DTIME(T(n)·log T(n))

为什么这里不能是 T(n)+1？ 为什么不是 T(n)·(1+ε)？ 为什么偏偏是 log n？

原因不是“技术巧合”，而是三重约束的交集：

---

1️⃣ 对角化需要“模拟开销”

层级定理的证明，本质是：

• 构造一台机器 M
• 它在时间 T(n)·log T(n) 内
• 模拟所有 T(n) 时间的机器
• 然后故意在某个点上和它们不一样

关键问题：模拟是要付账的。

即便是最乐观的情况：

• 你要读描述
• 你要计步
• 你要防止被无限循环骗

这些元操作的最低开销，几乎不可避免地是 log T(n) 级别。

低于 log 的增量，根本不够支付“监督模拟”的成本。

---

2️⃣ log n 是“最小的可放大函数”

在复杂度论里，有一类函数被叫做 constructible / honest functions。

log n 在这里是一个临界点：

• 它增长到无穷
• 但增长得极慢
• 又慢到你无法用常数技巧抹掉
• 快到你又能反复叠加、放大

相比之下：

• log log n 太慢，慢到对角化里常被“压平”
• √log n 虽然增长，但在很多构造中仍然不足以稳定承担模拟开销
• 任意 o(log n) 通常无法保证复杂度类严格扩张

log n 是第一个“稳态增长”的函数。

---

3️⃣ log n 是复杂度论中的“最小全局时间尺度”

你可以把时间复杂度想成三层尺度：

• 常数 / O(1)：局部行为
• log n：全局但轻量
• n^ε：真正线性世界的入口

log n 正好卡在：

• 不再是常数
• 又没进入“线性经济”

这使得它成为理论中最小的可检测差异。

---

三、那 log log n、√log n 呢？为什么不行？

你的问题问得非常精确：

它是否是简单复杂度函数中最小的一个增量？

在目前主流复杂度理论框架下，答案接近于：

是的，log n 是“可证明稳健”的最小增量。

更具体地说：

• 对任意 o(log n) 的增长 → 不存在普适的层级定理
• 对 log n → 层级定理成立，且形式优美
• 对 log^k n、n^ε → 更容易分离，但代价更大

这不是说 log log n 没意义，而是：

它太“轻”，轻到不足以稳定地区分计算能力。

---

四、算法世界与复杂度理论，在 log n 上悄悄握手

这件事的美妙之处在于：

• 在算法设计里 n → n log n 是“不可避免的排序税”
• 在复杂度理论里 T(n) → T(n)·log n 是“不可避免的对角化税”

两个完全不同的世界， 在 log n 这个点上，交汇了。

这通常意味着： 你看到的是某种深层结构，而不是偶然。

---

五、一句话总结（但不是结束）

log n 的特殊性在于：

• 它是信息论意义下的最小全局成本
• 是对角化与模拟的最低稳定开销
• 是第一个无法被常数技巧消去的增长
• 是复杂度类严格分离的最小通用增量

如果把复杂度函数想成一条地形图， log n 就是你第一次真正离开平原、但还没进山的那一步。

再往前走，世界会开始变得非常奇怪： log log n、AC⁰、TC⁰、细粒度复杂度、ETH、SETH…… 那里是另一片地貌，规则也开始变得不那么“干净”。

about \(P_{\setminus poly}\)

Miller Rabin

about BPP, BQP