内容
- 形式语言与自动机：正则语言、上下文无关语言、图灵机
- 可计算性：可判定、可归约
- 计算复杂性：时间、空间、难解性
正则语言
确定有穷自动机DFA：$M=<Q,Sigma,delta,q_0,F>,delta:Q imesSigma ightarrow Q$
- M 接受字符串：$w=w_1...w_n,exists q_0...q_n,delta(q_i,w_{i+1})=q_{i+1},q_nsubset F$
- 正则语言：A={w|w被一个 DFA接受}
- 正则表达式：$ain E, R_1R_2in E, (R_1|R_2)in E, R_1^*in E\,if\,R_1in E,R_2in E$
非确定有穷自动机NFA：$M=<Q,Sigma,delta,q_0,F>,delta:Q imesSigma ightarrow P(Q)$
- 任意 NFA，存在一个等价DFA
- 正则语言$Leftrightarrow$正则表达式
- 每个正则表达式存在一个 NFA 识别，或者一个 DFA识别，即正则语言
- 每个正则语言可用正则表达式定义
- $DFARightarrow GNFARightarrow$正则表达式
- 利用泵引理，证明一个语言不是正则的${1^n0^n}$
- 设 A 是一个正则语言，则存在一个数 p（泵长度），使得A中长度不小于 p 的字符串 s=xyz，$forall igeqslant 0,xy^izin A,|y|>0,|xy|leqslant p$
上下文无关语言
- 上下文无关文法CFG：$<V,Sigma,R,S>,R:V ightarrow (VigcupSigma)^*$
- 下推自动机PDA：$M=<Q,Sigma,Gamma,delta,q_0,F>,delta:Q imesSigma imesGamma ightarrow P(Q,Gamma)$
- 上下文无关语言$Leftrightarrow$被下推自动机识别
- 判定上下文无关语言的泵引理，反例${2^n1^n0^n}$
- 设 A 是一个上下文无关语言，则存在一个数 p（泵长度），使得A中长度不小于 p 的字符串 s=uvxyz，$forall igeqslant 0,uv^ixy^izin A,|vy|>0,|vxy|leqslant p$
图灵机
- 图灵机：$M=<Q,Sigma,Gamma,delta,q_0,q_{acc},q_{rej}>,delta:Q imesGamma ightarrow Q imesGamma imes{L,R},SigmasubsetGamma$
- 每个非确定的图灵机都有一个等价的确定图灵机
- Church-Turing假设：算法的直觉概念$Leftrightarrow$图灵机算法
- 线性界限图灵机：LBA 纸带长度等于输入个数
可判定
- 可判定：存在一个图灵机，对一个语言的任何输入都能停机（接受或者拒绝），该语言是图灵可判定$Leftrightarrow$图灵可识别 and 补图灵可识别。
- 可判定语言：$A_{DFA}, A_{NFA}, A_{REX}, EMPTY_{DFA}, EQUAL_{DFA}, A_{CFG}, EMPTY_{CFG}, A_{LBA}$
- 停机问题：$ATM={<M,w>|M\,is\,a\,TM，accept\,w} $可识别，不可判定
- 对角线方法：假设一个可数序列，其始终与第n行、第n列上的不一致。
- 存在图灵不可识别语言：图灵机集合是可数的，语言集合是不可数，因此语言与图灵机不可能一一对应。
- 不可判定：$EMPTY_{TM}, HALT_{TM}, EQUAL_{TM}, EMPTY_{LBA} 采用归约函数证明
可归约
- 函数$r:Sigma^* ightarrowSigma^*$可计算，如果有图灵机M，在每个输入 w 上，M 停机，此时只有 r(w)出现在纸带上
- 函数$T:N ightarrow N$，如果M在任意输入x上计算最多只需要$T(|x|)$个步骤，则称M在$T(n)$时间内计算 r。
- 语言 A 映射可归约到语言 B 如果存在可计算函数 f， $,forall w,win ALeftrightarrow f(w)in B$，记为$Aleqslant_m B$
- 此时，如果B可判定，则A也可判定；如果B图灵可识别，则A也图灵可识别。
时间
- 复杂度：函数$f,g:N ightarrow N,f(n)=O(g(n)),if\,f(n)leqslant C*g(n);f(n)=o(g(n)),if\,f(n)<C*g(n);$。
- 时间复杂类：$DTIME(t(n))={L|L $是确定型图灵机$O(t(n))$时间判定的语言$},NTIME(t(n))={L|L $是非确定型图灵机$O(t(n))$时间判定的语言$},where\,t:N ightarrow N$
- P类：$igcup_kTIME(n^k)$
- NP类：$igcup_kNTIME(n^k)$，或者可用确定型图灵机在多项式时间内验证。
- EXP类：$igcup_kTIME(2^{n^k})$
- 归约：语言 A 可多项式时间归约到B，记为$Aleqslant_p B$，如果存在多项式时间可计算函数$f:Sigma^* ightarrow Sigma^*,forall w,win ALeftrightarrow f(w)in B$。
- NP完全类：$Bin NP wedge forall Ain NP, Aleqslant_p B$。SAT是NP完全的。
空间
- 空间复杂度：函数$T:N ightarrow N$，如果 M 在任意输入x上计算最多只需要$T(|x|)$个方格，则称M在空间$T(n)$内计算。
- $SPACE(f(n))$：可用确定型图灵机在f(n)空间内判定。$PSPACE=igcup_kSPACE(n^k)$
- $NSPACE(f(n))$：可用确定型图灵机在f(n)空间内验证。$NSPACE=igcup_kNSPACE(n^k)$
- 萨维奇定理：任何函数$f:N ightarrow N，f(n)leqslant n, NSPACE(f(n))subseteq SPACE(f^2(n))$
- $Psubseteq NPsubseteq PSPACE=NPSPACEsubseteq EXPTIME$
- PSPACE完全类：$Bin PSPACE wedge forall Ain PSPACE, Aleqslant_p B$。
- TQBF 问题：TQBF={$<phi>|phi$是真的全量词化布尔表达式} PSPACE 完全。
- $L=SPACE(log n),NL=NSPACE(log n),coNL=NLsubseteq P$
- NL完全性：$Bin NL wedge forall Ain NL, Aleqslant_LB$
难解性
近似算法 概率算法 交互式证明系统 并行计算 密码学
参考文献
- Michael Sipser，Introduction to the Theory of Computation，Course Technology, 2005
- Sanjeev Arora, Boaz Barak, Computational Complexity, an modern approach, Cambridge University Press, 2015.11