简介：这份文档面向计算机专业本科生，尤其针对哈尔滨工程大学《计算理论》期末备考，把教材中分散的定义、定理与判定结论整理成可直接背诵的条目，便于考前集中突击与查漏补缺。内容以自动机理论开篇，覆盖正则语言与有穷自动机、确定型与非确定型自动机的等价性及封闭性；随后整理图灵机的格局、图灵可识别与可判定、判定器与丘奇—图灵论题；语言理论部分串联正则语言、上下文无关语言、下推自动机与乔姆斯基范式的对应关系；复杂度部分归纳 P 类、NP 类、SAT 与 3SAT、多项式时间归约、映射可归约性，以及停机问题、EQTM、PCP 等不可判定实例。整包仅含 1 个 docx 文件，约 18KB，篇幅轻巧，适合手机翻阅或打印成小册子随身背。目前已有 553 人学习，适合希望用最短时间过一遍考点的同学。

1. 计算理论是什么：一台想象中的机器，凭什么给“能算”划一条线

很多人第一次听到“计算理论”，以为是教人怎么用电脑算数的课。真翻开书才发现，整本书没有一行能跑起来的程序，全是“语言”“自动机”“可判定”这类离键盘很远的词，难怪期末复习时它常被吐槽成玄学。

通俗地说，计算理论研究的不是“怎么算得快”，而是“什么样的东西算得出来、要付出多大代价才算得出来”。打个比方，它像交通规则而不是驾驶技术：不教你怎么踩油门，只告诉你哪条路根本走不通。

搞懂它的价值很实在：你会知道有些问题不是程序员不够努力，而是数学上压根没有通用解法；也会知道另一些问题只是暂时没找到快办法，并非做不到。这份资料把散落的知识点按结论排好了，但背下来之前，先弄清楚每条结论到底在说什么。

2. 有穷自动机与正则语言：记忆只有几个格子，还能认出什么

2.1 有穷自动机把“记忆”压缩到几个状态

小区门口的刷卡闸机是个好类比。它不关心你叫什么、今天来了几次，只关心一件事：这张卡刷过没有。刷过就开，没刷过就拦。这种“只记当前走到哪一步、不记历史”的机器，就是有穷自动机。所谓“有穷”，指的是它能记住的状态数量在造出来那一刻就定死了，跟输入有多长完全无关。

确定型有穷自动机（DFA）的骨架由五样东西构成：一个有限的状态集合、一张字母表、一个转移函数、一个起始状态、一组接受状态。运行方式朴素得近乎笨拙：读写头从最左边开始，每读一个字符就按转移函数跳到下一个状态，读完最后一个字符时看自己停在哪儿——在接受状态里就接受，否则拒绝。

# 一台只有两个状态的 DFA：数 0/1 串里 1 的个数是奇数还是偶数 # q0 表示"到目前为止 1 的个数是偶数"，q1 表示奇数 delta = { ("q0", "0"): "q0", ("q0", "1"): "q1", ("q1", "0"): "q1", ("q1", "1"): "q0", } start, accept = "q0", {"q0"} # 起始状态、接受状态集合 def run(s): state = start # 记忆只有这一个变量，没有别的 for ch in s: # 每次只读一个字符 state = delta[(state, ch)] # 转移函数决定下一站 return state in accept # 停机时落在接受状态才算接受 print(run("1011")) # False，三个 1 是奇数 print(run("1100")) # True，两个 1 是偶数

这段代码里，delta是转移函数，state是这台机器全部的“记忆”，accept是接受状态集合。注意循环体每读一个字符就把上一个字符彻底忘掉，这正是它和普通变量的分水岭：变量可以累加、可以存数组，而自动机的状态数写死了。记住这一点，后面很多结论就不用硬背。

拿它去认“a 的个数和 b 的个数相等”这种语言，立刻撞墙。要判断相等，机器必须数数，数到一百万就得有一百万个状态，直接违反“有穷”的设定。这不是设计得不够巧妙，而是模型本身就不给你这个能力。

2.2 并、连接、星号：为什么拼起来还是正则语言

正则语言在并、连接、星号三种运算下封闭。封闭的意思很朴素：拿正则语言做这三件事，结果仍然是正则语言，不会掉出这一层。这在工程上等于一张“模块化许可证”，可以拆开设计再拼回去。

并运算对应“任选其一”。想认 L1 ∪ L2，就造一台非确定型有穷自动机，在起始处开两个分支，分别跑 L1 和 L2 的机器，任何一支接受就接受。连接对应“先后顺序”：先跑 L1 的机器，它接受后把控制权交给 L2 的机器接着跑。星号对应“重复任意次”：允许把 L 的机器反复跑，一遍、两遍、一百遍都行。

麻烦出在“零遍”上。星号的定义是任意有限次重复的拼接，包括 0 次，而 0 次拼接的结果不是“什么都没有”，是一个长度为零的空串 ε。所以 L* 里永远包含 ε，哪怕 L 本身是空集。

注意：∅ 表示“一个串都没有”，{ε} 表示“有一个长度为零的串”，这两者不是一回事。空集连接到任何集合上得到的仍是空集，空串连接到一个串上则不改变那个串。

这条区别在期末卷子上是高频翻车点。有人写“L* 可能是空集”，一写就错。真正要建立的习惯是：把“集合层面的空”和“串层面的空”分开想，前者是没有任何元素，后者是有元素但长度为 0。

封闭性还有一层实用价值。真实项目里判断一段输入是否合法，往往是若干条规则的组合：邮箱格式、日期格式、编号格式。如果每一小块都能写成正则表达式，并、连接、星号又都封闭，那么拼起来的大规则一定还能用同一套引擎处理，不会出现“拼完就没法编译”的尴尬。

2.3 NFA 和 DFA 等价：会“猜”不等于更强

非确定型有穷自动机（NFA）看起来比 DFA 厉害得多。同一个字符，它可以同时走好几条转移；它还允许 ε 转移，不读字符就悄悄换状态；碰到走不通的分支，它像会“猜”一样自动挑能走通的那条。初学时几乎都会有一个直觉：NFA 肯定比 DFA 能力强。

结论恰恰相反：每一台 NFA 都等价于一台 DFA，两者识别的语言完全一样，一个语言是正则的当且仅当有一台 NFA 能识别它。证明思路叫子集构造——把 NFA“当前可能处在的所有状态的集合”整体当成 DFA 的一个状态。NFA 有 k 个状态，DFA 最多有 2 的 k 次方个状态。

这张表最该记住的是最后两行：能力等价，代价不同。NFA 是“写起来舒服”，DFA 是“跑起来确定”。工程里的词法分析器通常先用 NFA 或正则表达式描述规则，再转成 DFA 执行，中间那步转换就是在为“确定性”付状态数的账。状态爆炸是真实存在的，某些规则的 DFA 会比 NFA 大出好几个数量级，这时候就得在内存和速度之间做取舍。

所以看到“非确定型”三个字，先别急着理解成“更强”。在这套理论里，它更像是一种描述上的便利，而不是能力上的升级。这个判断在后面图灵机那章还会再出现一次，形式几乎一模一样。

2.4 语言的分层：正则之上还有上下文无关

a 的 n 次方接 b 的 n 次方，这个语言是分层的经典分水岭。它要求 a 和 b 的数量严格相等，需要“数数”，而有穷状态记不住数，所以它不是正则语言。

但只要给它一个栈就行：每读一个 a 就压栈，每读一个 b 就弹栈，读完全部输入时栈恰好为空就接受。带栈的这台机器叫下推自动机，它识别的语言叫上下文无关语言。一个语言是上下文无关的，当且仅当存在一台下推自动机识别它；任何一个上下文无关语言，也都可以用乔姆斯基范式的上下文无关文法产生。

再往上还有一层关系：每一个正则语言都是上下文无关的。因为下推自动机可以压根不用它的栈，退化成一台有穷自动机。所以层级方向是正则被包含在上下文无关里，反过来不成立，a 的 n 次方接 b 的 n 次方就是那个反例。

这条包含链还会继续延伸。每一个上下文无关语言都是可判定的，因为下推自动机这种模型本身就保证能在有限步内给出答案。到这里，三层结构就清楚了：正则最“穷”，上下文无关多了栈，可判定语言再往上把“一定停機”也放弃掉。每一层都对应一类更强的机器，也对应一类更难的判定问题。

3. 图灵机：一条纸带、一个读写头，如何定义“可计算”

3.1 格局：把机器的“此刻”打包成一张存档

图灵机的构造很土：一条无限长的纸带、一个能读能写能左右移动的读写头、一个有限的状态寄存器。它每步做三件事——读当前格子、按转移规则改写、移动读写头并切换状态。

问题来了：怎么描述“计算进行到一半”这件事？答案是把三样东西捆在一起——当前状态、当前带上的全部内容、读写头当前的位置，这三者的组合称为图灵机的一个格局。打个比方，它就是游戏里的存档：读档之后，后面所有的剧情走向都能原样复现。

这个概念看着简单，却是后面一堆定义的基石。有了格局，才能把一次计算写成格局序列，才能讨论“接受计算历史”和“拒绝计算历史”。一台确定型机器在任何给定输入上最多只有一条计算历史，因为每步只有一种走法；非确定型机器则可能有多条，对应它同时展开的各个分支。计算历史一定是有限序列，这一点很关键：如果机器在某个输入上永不停机，那它既没有接受历史，也没有拒绝历史。

3.2 三种结局：接受、拒绝、循环

在一台图灵机上跑一个输入，可能出现三种结果：接受、拒绝、循环。前两种都好理解，机器进入对应的状态就停下来了。第三种要小心，这里的“循环”仅仅指机器不停机，并不一定是“永远重复同样的步骤”。它完全可以一直往右走、一直写新的符号，看起来忙得很，但永远不给答案。

这个细节特别容易被误解成“循环就是死循环、原地打转”。不是的。判断一台机器会不会停，靠的不是观察它有没有重复，而是要看它的规则集合。理论上的“循环”是一个纯粹的状态：没有停机，仅此而已。

也正因为“停机”这件事无法靠观察来确定，理论的关注点逐渐从“某台具体机器在这条输入上会不会停”，转向了“有没有一类机器，对任何输入都保证停”。后者就是下一节的主角。

3.3 识别与判定：差在“会不会一直转下去”

如果一个语言可能被某一台图灵机识别，就称它是图灵可识别的，也叫递归可枚举语言。这里的“识别”只承诺一件事：只要这个串属于该语言，机器最终会接受并停下来。至于不属于的串，机器可能拒绝，也可能一直转下去，不给你任何答复。

图灵可判定就严格得多，也叫递归语言。它要求存在一台机器，对任何输入都能停机，然后明确告诉你接受还是拒绝。这种所有输入都停机的机器叫判定器，说一台判定器判定某个语言，就是指它对每个输入都给出是或否的答案。

两者差一个字，含金量差一大截。每一个可判定语言都是图灵可识别的，反过来不成立。最典型的例子是图灵机接受问题：给定一台机器和一个串，问这台机器会不会接受这个串。这个问题可以被识别——你让机器跑起来，它一旦接受你就跟着说接受；但不可判定，因为如果它不停机，你没法区分“还要再等等”和“永远不会给答案”。判定器最难的地方就在这儿：它必须能区分“循环”和“只是算得很慢”，而这种区分在一般情况下做不到。

补集能帮上一点忙。一个语言的补，是由所有不在这个语言里的串构成的语言；如果一个语言的补是图灵可识别的，就说它是补图灵可识别的。有个漂亮的结论把三者串起来：一个语言是可判定的，当且仅当它既是图灵可识别的，又是补图灵可识别的。直觉上也说得通：要给出确定答案，你既要能确认“是”，也要能确认“否”。

3.4 多带、非确定型与丘奇-图灵论题

真实的机器不会只有一条纸带，所以理论里也定义了多带图灵机。结论是：每一台多带图灵机都等价于一台单带图灵机。等价的代价是时间变慢，模拟过程要来回搬动带子上的内容，原本 t 步能算完的，单带上大约要 t 的平方步。

非确定型图灵机同样如此：它能同时探索多条路径，看起来强得离谱，但每一台非确定型图灵机都等价于一台确定型图灵机。等价的方式是让确定型机器一条一条地模拟那些分支，代价是指数级的变慢。一个语言是图灵可识别的，当且仅当存在一台非确定型图灵机识别它；把“识别”换成“判定”，结论照样成立。

这一连串“等价”背后站着一个更大的命题：丘奇-图灵论题。它说的是，任何直观上能称为“算法”的东西，都可以用图灵机来实现。这不是一条能证明的定理，而是一个被广泛接受的约定，也是整门课敢用图灵机代表“计算”的底气。

顺带说一个复习时容易忽略的点：描述一台图灵机有三个层次。最底层是形式化描述，把状态、转移函数一条条写全；往上一层是实现描述，用日常语言说清楚每一步干什么，但不写转移表；最高层是高水平描述，连纸带和读写头怎么管理都不提，只讲算法思路。做题时先看清题目要哪一层，写多了浪费时间，写少了拿不到分，这是血泪经验。

3.5 归约：把不认识的问题翻译成认识的问题

归约是整门课最像“工具”的概念。映射可归约说的是：如果存在一个可计算的转换函数，把问题 A 的每个实例都变成问题 B 的一个实例，并且答案保持一致，就记作 A 映射可归约到 B。这里的可计算函数有严格定义：存在一台图灵机，对每个输入都停机，停机时带上恰好是转换结果。

方向感很重要。A 归约到 B，意味着“只要 B 有解，A 就有解”，反过来说 B 至少和 A 一样难。有了这个工具，两条推论可以直接用：如果 A 映射可归约到 B，且 A 是不可判定的，那么 B 也是不可判定的；如果 A 映射可归约到 B，且 B 是图灵可识别的，那么 A 也是图灵可识别的。

# 归约的骨架：假设已经有一个能解 B 的黑盒，怎么用它解 A def solve_A(instance_a): instance_b = f(instance_a) # f 必须是可计算函数，且处处停机 return solve_B(instance_b) # 答案必须与 A 的答案严格一致

这段骨架里有两处不能含糊。第一，f必须处处停机，否则你连转换这一步都可能卡死，归约就不成立。第二，答案必须严格一致，即原实例属于 A 当且仅当转换后的实例属于 B，差一点都不行。至于solve_B内部怎么实现，归约根本不管，这正是它的价值：把一个陌生问题翻译成一个已知问题，然后借用后者的结论。

靠着这套翻译，可判定与不可判定的清单被一条条攒了出来。

清单之外还有两个更细的结论：图灵机接受问题的补是不可识别的；两台图灵机是否等价这个问题，既不是图灵可识别的，也不是补图灵可识别的。后者常被拿来当反例，说明“可识别”和“补可识别”这两条路可能同时堵死。

4. 复杂度：P、NP、PSPACE 到底在比什么

4.1 时间复杂性类：用增长量级给机器分档

可判定性只回答“能不能算”，复杂度接着问“要花多少”。令 t 是一个从自然数到实数的函数，时间复杂性类 TIME(t(n)) 定义为所有能被运行时间为 O(t(n)) 的图灵机判定的语言组成的集合。换句话说，这一档里装的是“用这个量级的步数就能搞定”的全部问题。

模型换了，档位会不会变？会变，但不会变性质。每一台多带图灵机都和某一台运行时间为 O(t 的平方) 的单带图灵机等价；每一台运行 t(n) 步的非确定型单带图灵机，都和某一台运行 2 的 O(t(n)) 次方步的确定型单带图灵机等价。

平方从哪来？模拟多带时，单带机器得把几条带的内容挤在一条带上，每次访问远端数据都要走过去再走回来，来回的路费累积成了平方。指数从哪来？确定型机器模拟非确定型的多个分支时，最坏情况下要把每条分支都试一遍，分支数量随步数指数增长。

这两个换算关系是后面所有结论的地基。它们说明：换模型、换确定性，只会改变量级，不会把多项式变成非多项式之外的东西——平方还是多项式，指数就不是了。这也解释了为什么 P 类这个概念站得住脚：它不是某一台机器的性质，而是这一类模型共同的性质。

4.2 P 类与 NP 类：判定容易，还是验证容易

P 类是一类语言，它们在多项式时间内可判定。换句话说，存在一台图灵机，用多项式量级的步数给出是或否。上下文无关文法属于 P，路径问题属于 P，判断两个数是否互素也属于 P。这些问题的共同点是：答案能一步步算出来，不用猜。

NP 类的定义拐了个弯：一个语言在 NP 中，当且仅当它能被某台非确定型多项式时间的图灵机判定。非确定型机器会“猜”，所以这个定义翻译成人话是：如果答案是对的，存在一条猜测路径能在多项式时间内确认它。于是就有了那句广为流传的对照——P 是成员可以快速判定的语言类，NP 是成员可以快速验证的语言类。

# 验证一份证书：给一个赋值，检查它是否让每个子句都成立 def verify_3sat(clauses, assignment): for clause in clauses: # 每个子句是三个文字的或 if not any(lit_holds(lit, assignment) for lit in clause): return False # 有一个子句不满足，证书无效 return True # 全部满足，证书有效

这段验证代码只扫一遍公式，代价与公式规模成正比。也就是说，别人把答案递到你手上时，你确认它对不对很快；但从零开始找一个满足赋值，就得在指数级的组合里翻找。哈密顿路径、团、子集和、可满足性问题、三文字可满足性问题，全都落在 NP 里，它们的共同特征就是“验证不难，找解很难”。

需要提醒的是，NP 这个名字里的 N 指非确定型，不是“非多项式”。很多人第一次看到这三个字母，会把它理解成“多项式时间解决不了的问题”，这个理解是错的。P 类里的每一个问题都在 NP 里，因为能快速判定当然也能快速验证。真正的悬念是反方向包不包含，也就是 P 是否等于 NP。

4.3 多项式归约与 NP 完全：难题之间的“难度传递”

多项式时间可计算函数的定义是：存在一台多项式时间的图灵机，在任何输入上停机时，转换结果恰好出现在带上。如果存在这样的转换函数，让每个串属于 A 当且仅当转换后属于 B，就说 A 多项式时间映射可归约到 B，记作 A 多项式归约到 B，函数本身称为归约。

这套工具用来干什么？用来把“难”这个模糊感受变成可以传递的结论。如果 A 归约到 B，那么 B 至少和 A 一样难；一旦知道 A 是 NP 完全的，B 只要能接住这个归约，也就成了 NP 完全的。

库克-列文定理给出了第一块多米诺骨牌：可满足性问题是 NP 完全的。有了它，后面一串结论都是推出来的，比如三文字可满足性问题可以多项式时间归约到团问题，于是团问题也成了 NP 完全的。归约的方向必须记牢：是从已知难的问题出发，去证明新问题也难，反过来推不出任何东西。

可满足性问题的地位还体现在它和 P、NP 的关系上：只要可满足性问题有多项式时间算法，P 就等于 NP。这句话反过来也成立。所以整个 P 与 NP 之争，相当于把赌注全压在了一个问题上——这个看起来最单纯的逻辑公式求解，到底有没有快办法。目前没人找到，也没人证明找不到。

4.4 空间、萨维奇定理与复杂度类的阶梯

复杂度不只有时间一个维度。令 f 是一个从自然数到正实数的函数，空间复杂性类 SPACE(f(n)) 是所有能被 O(f(n)) 空间内的确定型图灵机判定的语言组成的集合；把“确定型”换成“非确定型”，就得到 NSPACE(f(n))。

空间这边有个很反直觉的结论，叫萨维奇定理：对任何满足 f(n) 不小于 n 的函数，非确定型图灵机能用 f(n) 空间解决的问题，确定型图灵机用 f(n) 的平方空间也能解决。也就是说，空间上的非确定性可以被压掉，只付出平方的代价。这条定理直接推出 PSPACE 等于 NPSPACE，非确定型在空间这一维没能撑起一个新层级。

空间里也有自己的“完全”问题。TQBF、公式博弈、地理游戏这几个是 PSPACE 完全的；路径问题是 NL 完全的。NL 是完全问题如果落在 L 里，那么 L 就等于 NL，这又是一场没打完的仗。

对数空间那一套还需要一个专门工具：对数空间转换器，它有一条只读输入带、一条只写输出带、一条读写工作带，工作带上只允许放 O(log n) 个符号。用它算出来的函数叫对数空间可计算函数，由它定义的归约叫对数空间归约。结论是：如果 A 对数空间归约到 B 且 B 属于 L，那么 A 也属于 L。

把这些层级摞起来，就得到那条经典链条：L 包含于 NL，NL 包含于 P，P 包含于 NP，NP 包含于 PSPACE，而 PSPACE 等于 NPSPACE。链条上每一个“包含于”都是已证明的，每一个能不能取等号，几乎都是一个悬而未决的大问题。

5. 五个最容易混淆的地方：名字像，含义差很远

5.1 易混一：图灵可识别当成图灵可判定

易混点：两个词都带“图灵”，都表示“机器能处理”，很多人复习时直接当成同义词。

为什么混：识别和判定在“接受”这一侧的表现完全一样。一个属于语言的串，两种机器都会接受并停机，你观察不出差别。差别只出现在不属于语言的串上：识别可能永远转下去，判定一定停下来给个“否”。

怎么区分：问自己一句“它保证停机吗”。保证，就是判定；不保证，只是识别。可判定语言一定可识别，可识别语言不一定可判定。典型的分界线是图灵机接受问题：它可识别但不可判定。再补一条判据，一个语言可判定当且仅当它和它的补都可识别，这条判据在判断“某个语言到底属于哪一档”时特别顺手。

5.2 易混二：以为非确定型比确定型更强

易混点：看到 NFA、非确定型图灵机，就以为它们能识别的语言更多。

为什么混：“非确定”这个词天然带着“更自由、更高级”的暗示，加上 NFA 确实能同时走多条路、能靠 ε 转移偷懒，直观上像是开了外挂。

怎么区分：能力等价，代价不同。每一台 NFA 都等价于一台 DFA，每一台非确定型图灵机都等价于一台确定型图灵机。转换的代价是状态数或时间可能指数级膨胀，但识别的语言集合分毫不差。所以看到“非确定型”，应该想到“描述更方便、模拟更昂贵”，而不是“能力更强”。真正决定能力强弱的是模型本身，比如有没有栈、纸带是不是无限，而不是转移动不动就分叉。

5.3 易混三：把正则语言和上下文无关语言的层级搞反

易混点：有人觉得正则表达式能描述很复杂的模式，就以为正则比上下文无关“更高级”；也有人看到上下文无关文法能描述嵌套结构，就以为它包含了正则。

为什么混：正则表达式在工程里用得太多，功能被各种引擎扩展得面目全非，给人“无所不能”的错觉；而上下文无关文法在教科书里出现得晚，容易被当成更基础的东西。

怎么区分：记住方向是正则被包含在上下文无关里，反过来不成立。识别器的对应关系也要钉死：正则语言对应有穷自动机，上下文无关语言对应下推自动机，多出来的那一个栈就是能力差距的来源。判断某个语言在哪一层，最省事的办法是找反例结构：需要数数的 a 的 n 次方接 b 的 n 次方不在正则里，但它在上下文无关里；需要两个计数器同步的语言，连上下文无关都保不住。

5.4 易混四：把归约的方向记反，以为它证明“两个问题一样难”

易混点：A 归约到 B，符号写起来像“A 小于等于 B”，于是有人理解成 A 比 B 简单，或者两个问题难度相当。

为什么混：不等号的直觉太强，加上归约确实建立了一种“难度比较”，很容易滑向“相等”。

怎么区分：A 归约到 B 只说明 B 至少和 A 一样难，不排除 B 更难。使用时方向必须盯紧：从 A 不可判定推出 B 不可判定，从 B 可识别推出 A 可识别，两条推论都是顺着归约箭头走的。反着用一定翻车，比如从 B 不可判定推不出 A 不可判定，因为 A 可能只是那个更简单的特例。做题时不妨在草稿上画个箭头，写上“难在上头”，比死记符号可靠。

5.5 易混五：以为 NP 就是“多项式时间解决不了”

易混点：把 NP 当成“难题集合”，以为凡是在 NP 里的问题都没有快算法。

为什么混：名字里的 N 看着像 Not，教材里举的例子又清一色是难问题，两个印象叠在一起就成了误会。

怎么区分：NP 的定义是“能被非确定型多项式时间图灵机判定”，等价说法是“解能快速验证”。P 类里每个问题都在 NP 里，它们显然都有快算法。真正没解决的是 P 是否等于 NP，也就是“快速验证”能不能升级成“快速求解”。另外，一个问题属于 NP，说的是它的解容易验证，不是说它一定难；只有被证明是 NP 完全的，才代表它是这一类里最难的那批。

6. 什么时候该搬出计算理论：一张边界判断表

6.1 值得搬出这套理论的三种场合

第一种是给别人解释“为什么这件事没有通用解法”。同事提了个需求，想让程序自动判断任意两段代码是否功能完全等价，或者自动找出让任意程序一定停机的检测方法。这类需求不是工期问题，而是撞上了不可判定性。这时候搬出图灵机接受问题和停机问题，比反复说“做不了”有说服力得多。

第二种是给工具的表示能力划边界。设计一个配置校验规则、一个日志过滤语法，你要清楚它停在哪一层：写成正则表达式就够的，别上完整文法；需要嵌套括号匹配的，正则一定不够，得换下推自动机那一档的思路。把这条线画在前面，能省掉后期大量返工。

第三种是看懂别人方案里的术语。技术文档里冒出“这个问题是 NP 完全的”“我们把它归约到 SAT 求解”，如果你不知道 NP 完全意味着什么，就判断不出对方是在陈述困难，还是在为某个近似方案找理由。期末复习时那些要背下来的结论，真正的作用也是这个：让你在读到一句话时知道它分量几何。

6.2 不必搬出这套理论的场合

反过来，日常写业务代码时，可判定性几乎帮不上忙。输入规模只有几十条记录，就算问题在理论上是指数复杂度，跑起来也可能只要几毫秒。理论说的是最坏情况下随规模增长的走势，不是你这台机器上这一刻的耗时。拿“NP 完全”去否掉一个实际可行的方案，属于用错了工具。

还有一类误用是把理论上的慢当成不能做。旅行商问题在理论上是难的，但加上“城市不超过十五个”这个约束，暴力枚举完全够用。真正该问的是：我的输入规模有多大，我能不能接受近似解，有没有利用数据本身的特殊结构。这三问比背复杂度类管用。

我自己的习惯是，每当想说“这个做不到”时，先在心里过一遍这张表：是理论上不可能，还是暂时没找到快办法，还是代价大到不划算。这三件事完全不同，混在一起说，讨论就会变成各说各话。从那以后，我每次遇到“某功能无解”的断言，都强制走一遍这个三选一，很多争论到这一步就自然消解了。

这份资料把上面这些结论按知识点整理成了一份可以直接对着复习的文档，需要的话拿走对着过一遍，比自己从教材里抠要快。希望帮到你。

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