从有穷自动机到图灵机：计算理论与P/NP复杂度入门

简介这份文档面向计算机专业本科生尤其针对哈尔滨工程大学《计算理论》期末备考把教材中分散的定义、定理与判定结论整理成可直接背诵的条目便于考前集中突击与查漏补缺。内容以自动机理论开篇覆盖正则语言与有穷自动机、确定型与非确定型自动机的等价性及封闭性随后整理图灵机的格局、图灵可识别与可判定、判定器与丘奇—图灵论题语言理论部分串联正则语言、上下文无关语言、下推自动机与乔姆斯基范式的对应关系复杂度部分归纳 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 次方个状态。对比项DFANFA同一字符的转移唯一确定可以有多条ε 转移不允许允许状态数量可能指数级膨胀通常更紧凑识别能力正则语言正则语言完全相同适合的用途直接跑、做词法分析描述方便、便于构造这张表最该记住的是最后两行能力等价代价不同。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 包含于 NLNL 包含于 PP 包含于 NPNP 包含于 PSPACE而 PSPACE 等于 NPSPACE。链条上每一个“包含于”都是已证明的每一个能不能取等号几乎都是一个悬而未决的大问题。类直观含义代表问题L对数空间可判定路径问题在无向图上更简单NL非确定型对数空间有向图路径问题P多项式时间可判定路径问题、互素判定、上下文无关语言NP多项式时间可验证哈密顿路径、团、子集和、可满足性问题PSPACE多项式空间可判定量词布尔公式、公式博弈、地理游戏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 完全”去否掉一个实际可行的方案属于用错了工具。还有一类误用是把理论上的慢当成不能做。旅行商问题在理论上是难的但加上“城市不超过十五个”这个约束暴力枚举完全够用。真正该问的是我的输入规模有多大我能不能接受近似解有没有利用数据本身的特殊结构。这三问比背复杂度类管用。场景该不该搬出理论判断依据要证明某功能对任意输入都不可能实现该撞上不可判定问题设计一门小语言的语法该需要确定表达力停在哪一层阅读方案里的复杂度标注该需要判断术语的分量处理几十条数据的业务逻辑不该规模小常数项主导给一个理论上的难问题找落地方案不该直接否决可近似、可约束、可利用结构我自己的习惯是每当想说“这个做不到”时先在心里过一遍这张表是理论上不可能还是暂时没找到快办法还是代价大到不划算。这三件事完全不同混在一起说讨论就会变成各说各话。从那以后我每次遇到“某功能无解”的断言都强制走一遍这个三选一很多争论到这一步就自然消解了。这份资料把上面这些结论按知识点整理成了一份可以直接对着复习的文档需要的话拿走对着过一遍比自己从教材里抠要快。希望帮到你。本文还有配套的精品资源点击获取