企业官网建设流程全解析

简介：面向计算机专业学生与备考者的「计算理论知识点」梳理文档，聚焦期末复习与考点速记，把自动机、图灵机、语言理论、计算复杂度等抽象内容压缩成可背诵的条目式结论，适合课堂笔记整理、考前突击与概念自查。资源包共1个文件，为18KB的docx笔记，按自动机与正则语言、图灵机与格局、可判定与可识别语言、归约与复杂度类等模块编排，涵盖正则语言的封闭性与等价性判定、判定器与丘奇图灵论题、映射可归约性与ATM、HALT、EQTM等不可判定问题，以及P、NP、SAT、3SAT、CLIQUE、HAMPATH、SPACE等复杂度结论，条目标注清晰，便于对照教材快速检索。目前已有553人学习下载。文档以短句罗列关键定义与定理，适合反复默写与查漏补缺，也可作为刷题时快速回查的索引清单。

1. 计算理论知识点地图：四层语言、三种模型、两条归约线

计算理论期末复习时，最容易出错的地方集中在把“识别”和“判定”当成同一件事，而“定理记不住”本身反倒不是主要问题——大量选择题和证明题的关键区别就集中在这一个词上。整门课其实是一张很规整的地图：横向是四层语言（正则包含于上下文无关，上下文无关包含于可判定，可判定包含于图灵可识别）；纵向是三种计算模型（有穷自动机、下推自动机、图灵机），再加上两条贯穿线——映射归约和复杂度类。在开始背诵这些内容之前，先确认自己能在纸上默画出这张包含关系图；如果画不出来，后面所有“可判定/不可判定”的判断都会变成猜测。这份笔记适合正在系统学、或者考前想把知识点过一遍的人。

2. 语言层级：正则、上下文无关与四层包含关系怎么串

语言层级是整个计算理论课程的基础。这一章的核心任务是把“什么模型识别什么语言”和“什么语言能被什么机器判定”这两件事分开记：前者是等价性定理，后者是可判定性定理。所以一旦把“识别”当成了“判定”，后面的所有判断都会跟着出错。梳理下来会发现，几乎所有结论最后都能归结到一张表上——只要这张表能默写，后面的图灵机和复杂度部分就只是在这张表上继续加了一层。

2.1 四层包含关系：一张表固定所有“包含于”和“不包含于”

先把四种语言类和它们的识别模型对应起来，注意第四列和第五列是两条不同的信息，不要混着背。

这张表背后是四条包含关系，每一条的证明思路都不一样：正则包含于上下文无关，因为 DFA 是不用栈的 PDA；上下文无关包含于可判定，因为把文法转成乔姆斯基范式后，长度固定的串只有有限多条推导可枚举；可判定包含于图灵可识别，因为判定器本身就是一个识别器，只是它保证停机。四条包含关系都是严格的：存在上下文无关但非正则的语言（0 的 n 次方接 1 的 n 次方），存在可判定但不是上下文无关的语言，A_TM 则是可识别却不可判定的代表。

提示：背这张表的时候，把“封闭性”和“可判定性”分成两栏单独默写。这两栏最容易被合并成一句“都挺封闭的”，然后在 EQ_CFG、ALL_CFG 这类题上出错。

2.2 正则语言的三件套：DFA、NFA、正则表达式为什么等价

围绕正则语言，核心是下面这组等价命题，它们互为不同方向，考试常拆成四道小题：

• 一个语言被有穷自动机识别，则它是正则语言；
• 一个语言是正则的，当且仅当有一台非确定型有穷自动机识别它；
• 一个语言是正则的，当且仅当有一个正则表达式描述它；
• 每一台非确定有穷自动机都等价于一台确定型有穷自动机。

前三条是“同一类语言的不同描述方式”，第四条是模型之间的等价，不是语言类的扩展。很多人误以为 NFA 比 DFA 强，其实二者识别的语言集完全相同，差别只在描述规模和构造便利度。子集构造就是这个等价性的构造性证明：把 NFA 的状态集合整体当作 DFA 的一个状态。

# 子集构造：NFA -> DFA，把"状态集合"当成 DFA 的单个状态 from collections import deque def eps_closure(states, eps): # eps: dict[state] -> set(state)，求 ε-闭包 stack, seen = list(states), set(states) while stack: s = stack.pop() for t in eps.get(s, ()): if t not in seen: seen.add(t) stack.append(t) return frozenset(seen) def nfa_to_dfa(delta, eps, start, accepts, alphabet): # delta: dict[(state, symbol)] -> set(state) d0 = eps_closure({start}, eps) # 起始状态要先做 ε-闭包 queue, seen, trans = deque([d0]), {d0}, {} while queue: cur = queue.popleft() for a in alphabet: nxt = set() for s in cur: # 集合里每个状态同时走 a nxt |= set(delta.get((s, a), ())) nxt = eps_closure(nxt, eps) # 走完再补 ε-闭包 trans[(cur, a)] = nxt if nxt not in seen: seen.add(nxt) queue.append(nxt) # DFA 的接受态 = 含有任一 NFA 接受态的集合 dfa_accepts = {S for S in seen if S & accepts} return seen, trans, d0, dfa_accepts

这段代码里有三个参数值得单独记：delta是符号转移表，eps是空串转移，alphabet是字母表。只要alphabet给全，构造出来的 DFA 就是完备的；如果漏了某个符号，就会得到一个“缺边”的自动机，后面做乘积构造求交、求补时会出错。还有一点：状态数最坏是 2 的 n 次方，所以“等价”不等于“规模不变”，这也解释了为什么正则表达式在实际中更常用。

封闭性同样要能当场构造：并、连接、星号是题目里明确要求的三个，做法分别是引入新起始状态分叉、串接、以及加 ε 边回环。并运算的构造是“新起点 ε 分叉到两台机器”，连接是“前一台的接受态 ε 连到后一台的起点”，星号是“接受态 ε 回起点 + 新起点兼新接受态并带 ε 到旧起点”。这三种 ε 边构造法几乎可以套用到所有封闭性证明，记住模板比背结论有用。

2.3 上下文无关语言：乔姆斯基范式与下推自动机的对应关系

上下文无关这一层有两个必须背下来的等价刻画，它们分别对应“文法侧”和“机器侧”：

• 任何一个上下文无关语言都可以用乔姆斯基范式的上下文无关文法产生；
• 一个语言是上下文无关的，当且仅当存在一台下推自动机识别它。

乔姆斯基范式的形式是每条规则形状为 A → BC（两个变量）或 A → a（一个终结符），并且语言中不含空串时不需要 A → ε 这条规则。这个限制看起来是“削弱”，实际是“规范化”：一旦所有规则都是二叉或单终结符形式，任何长度为 n 的串（n ≥ 1）的推导步数就固定为 2n - 1 步，这个数字是后面 A_CFG 可判定性证明的关键。换句话说，乔姆斯基范式不是为了好看，而是为了给“枚举推导”这件事一个有限上界。

下推自动机这一侧要记的是等价性而非细节：PDA 的两种接受方式（终态接受、空栈接受）互相可转换，所以“存在一台 PDA 识别它”这个措辞里并不区分是哪一种。做题时如果题目给的是空栈接受，转成终态接受只需加一个“栈底符号出现则进入接受态”的收尾状态，反之亦然。这里最容易忽略的是“ε 转移”的处理：PDA 允许在不读输入的情况下改栈，这也正是它能处理 0 的 n 次方接 1 的 n 次方这种需要“计数”的语言、而 DFA 不行、图灵机又能轻松做到的原因。

顺带把包含关系再固定一次：正则语言包含于上下文无关语言，因为 DFA 可以看成一抬永不使用栈的 PDA，或者由正则文法（右线性文法）直接写出 CFG。反向不成立，经典的 0 的 n 次方接 1 的 n 次方就是反例。

2.4 这一层的可判定性：A_CFG 与 E_CFG 为什么都能判

先记住结论：A_CFG（给定文法 G 和串 w，判断 w 是否由 G 产生）可判定，E_CFG（判断文法产生的语言是否为空）可判定，由此还得到一条常考结论——每一个上下文无关语言都是可判定的。

A_CFG 的判定思路正是上一节留下的线索：把 G 转成乔姆斯基范式，然后枚举所有长度恰好为 2|w| - 1 的推导。由于每条规则最多引入两个变量，长度为 |w| 的串的推导步数被卡死在 2|w| - 1，枚举是有限的，逐条比对即可。注意这里枚举的是“所有可能的推导”，数量随 |w| 指数增长，但有限就是可判定，复杂度问题留到后面的 P、NP 部分再谈。

E_CFG 的判定用的是标记算法：先把所有能推出终结符串的变量标记出来（形如 A → a 的规则先标），然后反复应用形如 A → BC 的规则——只要 B 和 C 都被标记过就标记 A，直到不再变化。最后检查起始变元是否被标记：没被标记，说明语言为空。这个“反复扫描到不动点”的模式在计算理论里出现频率很高，和后面找可达状态、判断空语言是同一套思路，值得单独记成一个通用方法。

3. 图灵机与可计算性：格局、判定器与三种运行结果

从有穷自动机跳到图灵机，最大的变化不是多了一条可以左右移动的带子，而是“停机”变成了一个需要单独讨论的问题。前面两层语言里，机器读完输入自然会给出答案；到了图灵机，机器可能永远不停。这一章要解决的就是把“运行过程”这件事变成可以写下来、可以比较、可以证明的对象。

3.1 格局与计算历史：把一次运行压缩成可枚举的序列

格局的定义必须一字不差地记住：图灵机计算过程中，当前状态、当前带内容和读写头当前位置，这三样组合在一起称为图灵机的格局。它本质上是一个瞬时快照，把无限长的带子（实际只有有限个非空白符号）和状态打包成一个有限对象。

在此之上是计算历史：设 M 是一台图灵机、w 是一个串，M 在 w 上的一个接受计算历史是一个格局序列 C1、C2、……、Cl，其中 C1 是 M 在 w 上的起始格局，Cl 是一个接受格局，并且每个 Ci 都是 Ci-1 一步之后的结果、符合 M 的转移规则。把“接受”换成“拒绝”，就是拒绝计算历史的定义。

这两条定义最有价值的地方在于两条性质。第一，计算历史都是有限序列——它是按步编号的，不允许无限长。第二，如果 M 在 w 上永不停机，那么 M 在 w 上既不存在接受历史，也不存在拒绝历史。这里就有一个很好用的推论：确定型机器在任何给定输入上最多只有一条计算历史；非确定型机器即使在单个输入上也可能有多条计算历史，它们与各个分支一一对应。所以判断“是否存在接受历史”在给定步数上限时是可判定的——枚举所有长度不超过该上限的格局序列即可；麻烦只在于步数上限没有先验值，这个“无界”正是 A_TM 不可判定的根源。

提示：写不可判定性证明时，把计算历史当成“证据”来用。存在性可以验证，但不存在性无法通过有限枚举证明，这句话几乎能解释所有可识别与不可判定的分界。

3.2 接受、拒绝、循环：判定器为什么是分水岭

在给定输入上运行一台图灵机，只有三种可能：接受、拒绝、循环。这里的循环专指机器不停机，不一定是“永远重复同样的步骤”那种字面意义上的转圈——它可能一直在往前走，只是永远走不到终点。所以图灵机有两种不接受的方式：进入拒绝状态而拒绝，或者干脆不停机。

判定器和识别器的区别就在这一处。判定器是所有输入都停机的图灵机，它永远不循环，总能明确地给出接受或拒绝；识别器只保证“接受时一定停机”，拒绝时可能永不回来。因此有了两条方向相反的包含关系：每一个可判定语言都是图灵可识别的，但反过来不成立。A_TM 是图灵可识别的，却不是可判定的，这个例子几乎是所有证明题的起点。

再往下一层是补运算。一个语言的补，是由不在此语言中的所有串构成的语言；如果一个语言的补是图灵可识别的，就称原语言是补图灵可识别的。于是有一条很好用的判别式：一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。这条结论的用法非常固定——想证某个语言不可判定，就去证它可识别但补不可识别，或者两边都不可识别（EQ_TM 就是既不是图灵可识别的、也不是补图灵可识别的典型）。

3.3 丘奇-图灵论题与三种描述水平

丘奇-图灵论题给出的就是算法的明确定义：凡是直观上可计算的，都能用图灵机计算。它不是一个可以证明的定理，而是一条被接受的约定，所有关于“可计算性”的结论都建立在它之上。考试里出现“为什么可以用图灵机定义算法”这类问法时，答的就是这条论题的地位。

配套的是描述水平的三档区分，这一条很多人只记了名字不会用：

关键点是：三种描述水平描述的仍然是同一类机器，高水平描述不是“另一种模型”。丘奇-图灵论题保证了只要算法能用日常语言说清楚，就存在对应的图灵机，所以证明里大量使用高水平描述是合法的，并不是偷懒。翻车点在于把高水平描述用在了要求“形式化给出转移函数”的题目上——那不是描述水平问题，而是没答到点子上。

3.4 等价性结论清单：多带、非确定型与线性有穷自动机

这一组结论最好做成一张表来记，因为它们在复杂度那一章会以“代价”的形式再出现一次。

“等价”这个词在这里有两层含义：识别能力上完全一样，代价上却可能差一个量级。多带转单带是平方级，非确定转确定是指数级，这两个数字必须和结论绑在一起记，因为后面 P 与 NP 的定义、萨维奇定理的表述都直接引用它们。

线性有穷自动机（LBA）是受限的图灵机：它不允许读写头离开包含输入的那段区域，如果机器试图把头移出输入的两个端点，头就原地不动——这和普通图灵机读写头不会移出带子左端点是同一种处理方式。它的位置很微妙：A_LBA 是可判定的（状态数乘上带内容组合是有限的，可以判定是否重复格局），但 E_LBA 却不可判定。一个受限模型反而在“空语言”问题上变得不可判定，这是这一节最容易记反的一对。

4. 归约与复杂度：映射归约、P/NP、PSPACE 与 NL

如果说前三章是在“描述计算”，这一章就是在“比较计算”。归约是把一个问题换成另一个问题，复杂度是把机器跑的步数或格子数换算成函数增长。两条线合在一起，才有了可判定性清单和 P、NP、PSPACE 的那条包含链。

4.1 映射归约：≤m 的定义与两条传递定理

映射归约的定义要背到能默写的程度：语言 A 映射可归约到语言 B，是指存在一个可计算函数 f，从串映射到串，使得对每个 w 都有 w 属于 A 当且仅当 f(w) 属于 B，记作 A ≤m B，这个 f 称为 A 到 B 的归约。它背后的直觉是：如果有了这个转换函数，就能用 B 的解决方案来解决 A——遇到 A 的实例，先用 f 转成 B 的实例，再调用 B 的解法。

这里有一个前置概念：函数 f 是可计算函数，是指存在某台图灵机 M，使得每个输入 w 上 M 都停机，且停机时只有 f(w) 出现在带上。注意“停机”这个词——可计算函数要求处处停机，这正是它和“可识别”的区别。归约函数必须是可计算的，否则整个归约没有意义。

两条传递定理是使用频率最高的工具，但方向必须严格按原样记：

• 如果 A ≤m B 且 A 是不可判定的，则 B 也是不可判定的；
• 如果 A ≤m B 且 B 是图灵可识别的，则 A 也是图灵可识别的。

第一条是“把不可判定性沿归约方向推过去”，第二条是“把可识别性沿归约反方向拉回来”，所以第二条例题的逆否形式——A 不是图灵可识别的，则 B 也不是图灵可识别的——在证明里同样常用。实际做题的标准流程只有三步：选一个已知不可判定的 A，构造可计算的 f，验证 w 属于 A 当且仅当 f(w) 属于 B。三步里最容易漏的是第三步的“双向验证”，只证了一个方向就当完成，是常见的得分点丢失。

4.2 不可判定性清单：从 A_TM 到 PCP 谁站在哪一边

这张表建议整张抄下来，考前只默这张表。

这张表的记忆逻辑可以分三层。第一层是“有穷结构可枚举”的都算可判定：DFA、NFA、正则表达式、CFG 都是有限对象，检查它们与给定串的关系只需要有限搜索，所以 A_DFA 到 E_CFG 全部可判定。第二层是“涉及图灵机行为”的几乎都不可判定：A_TM 是源头，HALT_TM、E_TM、REGULAR_TM、EQ_TM 都靠归约从它推出来。第三层是“两个方向都不行”的极少数：A_TM 的补不可识别，EQ_TM 两边都不是。

证明骨架也值得单独记一遍：不可判定性证明几乎都走“假设有判定器，再构造一个自指式的矛盾”这条路，或者从 A_TM 直接归约过去。计算历史在这里扮演关键角色——把“M 在 w 上接受”编码成一个格局序列，再用图灵机去检查这个序列的相邻两项是否符合转移规则，就把 A_TM 归约成了某个看起来更“结构化”的问题。PCP 就是这条路走到底的产物，它的不可判定性再往下推，可以带出一大批形式语言与自动机相关的不可判定问题。

注意：A_LBA 可判定但 E_LBA 不可判定，这一对必须单独记。凡是把“受限”当成“更简单”的直觉，在这里都会出错。

4.3 时间复杂性：P、NP 与多项式时间归约

时间复杂性类的定义是：令 t 是从自然数到实数的函数，TIME(t(n)) 表示能被时间 O(t(n)) 的图灵机判定的所有语言的集合。注意这里用的是“判定”，谈复杂度的时候默认机器是判定器，因为只有总停机的机器才能给出一个确定的运行时间上界。

两个换算结论必须记准，它们和第三章的等价性是一一对应的：

• t(n) ≥ n 时，每一个多带图灵机都和某一个 O(t²(n)) 时间的单带图灵机等价；
• t(n) ≥ n 时，每一个 t(n) 时间的非确定型单带图灵机，都与某一个 2 的 O(t(n)) 次方时间的确定型单带图灵机等价。

P 类就是这个框架下最干净的一个类：在多项式时间内可判定的语言类。PATH 属于 P，RELPRIME 属于 P，每一个上下文无关文法也属于 P。NP 的原始定义走的是非确定型路线——一个语言在 NP 中，当且仅当它能被某个非确定型多项式时间的图灵机判定。而更常用的直觉版本是：P 是成员可以快速判定的语言类，NP 是成员可以快速验证的语言类。这两个说法在考试里都合法，但前者是定义，后者是等价刻画，回答“用定义说明”的题时要写前者。

# NP 的"快速验证"视角：给定证书，多项式时间检验 def verify_subset_sum(nums, target, cert): # cert 是下标集合，也就是"证书"，长度不超过 len(nums) if any(i < 0 or i >= len(nums) for i in cert): return False # 下标越界，证书非法 if len(set(cert)) != len(cert): return False # 重复下标，证书非法 return sum(nums[i] for i in cert) == target # 校验和是否等于目标 # 验证是 O(n) 的，但"找出这个 cert"没有任何已知的多项式算法

这段代码想说明的就是 P 与 NP 的分界位置：验证器本身是多项式时间的，难点在找证书这一步属于搜索。把“能快速验证”直接读成“能快速判定”，是这一章非常典型的一处理解偏差。

多项式时间归约的定义要和非多项式版本区分开：语言 A 多项式时间映射可归约到语言 B，记作 A ≤p B，是指存在多项式时间可计算函数 f，对每个 w 都有 w 属于 A 当且仅当 f(w) 属于 B；这里的可计算函数还要求存在多项式时间图灵机，在任何输入 w 上停机时 f(w) 恰好出现在带上。NP 完全的标准构造链是 3SAT 多项式时间可归约到 CLIQUE，SAT、3SAT、CLIQUE、HAMPATH、UHAMPATH、SUBSET-SUM 都在 NP 里。

库克-列文定理的表述要小心：它说的是 SAT 是 NP 完全的，由此得到一个推论——SAT 属于 P 当且仅当 P = NP。很多人抄着抄着就写成“SAT 属于 P”，把推论写成了定理本身，这在概念题里会丢得很干脆。

4.4 空间复杂性：萨维奇定理、PSPACE 完全与 NL 完全

空间侧的定义和时间侧对仗：令 f 是从自然数到正实数的函数，SPACE(f(n)) 是所有能被 O(f(n)) 空间的确定型图灵机判定的语言集合，NSPACE(f(n)) 则是把确定型换成非确定型。萨维奇定理给出两者之间的关系：对任何 f(n) ≥ n，NSPACE(f(n)) 包含于 SPACE(f²(n))。也就是说，非确定型在空间上只需要平方的代价就能转成确定型——这和“非确定转确定在时间上要指数”形成了鲜明对比，是最值得反复提醒自己的一处不对称。

PSPACE 完全的代表是 TQBF、FORMULA-GAME、GG，NL 完全的代表是 PATH。在 NL 这一层要引入对数空间转换器的概念：它有一条只读输入带、一条只写输出带和一条读写工作带，工作带上只允许 O(log n) 个符号；由它计算的函数称为对数空间可计算函数。如果语言 A 通过对数空间可计算函数映射归约到 B，就称 A 对数空间可归约到 B，记作 A ≤L B。它同样有传递性：如果 A ≤L B 且 B 属于 L，则 A 属于 L。

NL 完全的定义还有一个很好用的推论：如果有一个 NL 完全语言属于 L，那么 L = NL。这条例题的价值在于，它把“两个类是否相等”这种宏大问题，压缩成了“某一个具体语言落在哪一边”的问题，思路和 P 与 NP 完全的关系完全平行。

最后是那条必须能默画的包含链：

• L 包含于 NL，NL = coNL，NL 包含于 P，P 包含于 NP，NP 包含于 PSPACE，PSPACE = NPSPACE。

这条链里唯一确定相等的两处是 NL = coNL 和 PSPACE = NPSPACE（后者的依据正是萨维奇定理），其余都是真包含“是否严格”尚未确定的开放问题。

5. 易错点排查：五处一考就出错的概念边界与推导方向

这一章只收集错误率最高的五类问题，每一条都按“易漏点、为什么容易漏、怎么补”的顺序写。

5.1 语言与模型类：三个容易被含糊表述带过的边界

第一处：把“识别”和“判定”混为一谈。容易漏在题干措辞上——“被某台图灵机识别”和“被某台图灵机判定”只差一个字，答案却完全不同。为什么容易漏：日常语言里“识别出来”和“判断出来”几乎是同义的，加上 A_TM 这个可识别不可判定的例子太出名，反而让人记住了结论、忘了条件。怎么补：每次看到“识别”，立刻在草稿上补两个字“可不停机”；看到“判定”，补“必定停机”。然后过一遍那条判别式：可判定当且仅当图灵可识别且补图灵可识别。用这条判别式反推，比背结论稳。

第二处：空集和空串分不清。容易漏在连接运算上。空集连接到任何集合上得到空集，而空串连接到任何一个串上不改变这个字符串——这两句话形式相似，含义完全相反。为什么容易漏：符号上 ∅ 和 ε 都很“小”，写起来顺手，做题时容易把 {ε} 当成 ∅。怎么补：牢记 {ε} 不是空集，它含一个元素，因此它的长度是 0 但基数不是 0；判断某个语言是否为空时，先看它是否含 ε，再谈别的。乔姆斯基范式那一节也牵连到这里：语言含 ε 时需要额外的一条 A → ε 规则，不含 ε 时才能用纯二叉规则，这个前提条件很多人会漏写。

第三处：乔姆斯基范式的适用范围。容易漏在“任何上下文无关语言都能转成乔姆斯基范式”这句话的附加条件上。为什么容易漏：定理通常只写前半句。怎么补：记住转换时先消除 ε 规则和单位规则，再处理含 ε 的情形；一旦题目要求“用推导步数为 2|w|-1 论证”，就要检查 w 是否为空串，空串要单独处理。

5.2 归约与复杂度类：两个方向和一个笔误

第四处：归约方向用反。容易漏在传递定理的使用条件上。为什么容易漏：A ≤m B 的箭头方向是“A 归约到 B”，但结论里“B 不可判定”推出的却是 A 的坏消息没有、B 的坏消息才有，方向感很容易打结。怎么补：把两句话写在一起对照——“A 不可判定 ⇒ B 不可判定”是把坏消息推过去，“B 可识别 ⇒ A 可识别”是把好消息拉回来。再用一个具体例子锚定：A_TM ≤m HALT_TM，A_TM 不可判定，所以 HALT_TM 不可判定；反过来想用 HALT_TM 的不可判定去说 A_TM 不可判定，就绕远了，虽然结论对但证法不干净。

第五处：平方和指数记反，以及把库克-列文定理写成“SAT 属于 P”。这两条放在一起，因为都是记忆层面的串味。为什么容易漏：多带转单带、非确定转确定，两组结论形式相似，代价一个是 O(t²)、一个是 2 的 O(t) 次方，抄写时极易互换。怎么补：给它们各自绑一个记忆句子——“带子变少是多项式代价，分支变少是指数代价”，因为合并带子只是把并行改成顺序，而消除非确定性本质上是把所有分支都跑一遍。库克-列文那条则记成一句完整的话：SAT 是 NP 完全的，因此 SAT 属于 P 当且仅当 P = NP；只说前半句是定理，只说后半句是推论，两句都写才完整。

把这五条抄在一张卡片上，每次做套题前扫一眼，比再做十道新题有效。

6. 复习清单：按三轮过一遍的查漏补缺方案

真正的查漏补缺不是把笔记再读一遍，而是按“能否脱离资料默写”来分层。给一个可以直接照做的三轮安排，每轮不超过两小时。

第一轮只做“结构性回忆”，目标是能把四层包含关系和三种模型的对应关系画出来。具体动作：白纸上写正则、上下文无关、可判定、图灵可识别四行，每行补出识别模型、等价描述、一个典型判定问题，然后在这张表下面补三种模型的等价性结论（多带与单带、非确定与确定、LBA 的定位）。画不出来的格子就是漏洞，直接回到对应章节补。

第二轮做“清单式核对”，用下面这张表逐条打勾，只勾“能默写”，不勾“看着眼熟”。

第三轮只攻错题。把这一周做错的题按“概念错、方向错、笔误”三分类，概念错回到第 2 到第 4 章对应小节，方向错集中在第 4 章的归约和第 5 章的五个易错点，笔误类只做一件事——把容易串的符号列成对照卡，比如 ∅ 与 {ε}、≤m 与 ≤p、可识别与可判定，每天早上扫一遍。

最后说个自己的教训。第一次做套题的时候，我在一道“证明某语言不可判定”的题上写满了归约构造，检查时才发现在第二步，函数并不是处处停机，只是“在需要的时候才停”；整个证明因此无效。从那以后我每次构造归约函数，都强制走一遍三个问题的自检：函数是不是对每个输入都停机？w 属于 A 当且仅当 f(w) 属于 B 的双向都验证了吗？我引用的那条传递定理，箭头方向和我用的方向一致吗？这三问只花一分钟，却能挡掉大部分失分。希望帮到你。

本文还有配套的精品资源，点击获取