到目前为止本专栏讨论近似算法的视角一直是“建设性”的——我们为集合覆盖设计了贪心近似为最大割分析了局部搜索为背包问题构造了FPTAS。这些工作回答的是“我们能近似到多好”。但还有另一个同等重要的问题“我们为什么不能近似得更好”当算法设计者反复尝试突破某个近似比却屡屡失败时究竟是技巧不够还是问题本身就设置了一道不可逾越的壁垒不可近似性理论给出的回答是在P≠NP的假设下许多问题的近似难度确实存在严格的下界——这些下界不是猜测而是可证明的定理。而这一切的源头是一条名为PCP的深刻定理。一、从NP的证书验证到PCP局部可验证的证明回顾第41篇中NP的证书验证定义L∈NPL∈NP 当且仅当存在一个多项式时间验证器 VV对于 x∈Lx∈L存在证书 yy使得 V(x,y)1V(x,y)1对于 x∉Lx∈/L对任意 yyV(x,y)0V(x,y)0。验证器需要阅读整个证书才能做出判断——证书的任意一个比特都可能影响验证结果。PCP定理的核心洞见是验证器其实不需要阅读整个证书。它可以随机抽取证书的常数个位置进行检查如果 x∈Lx∈L存在一个证书使得验证器以概率1接受如果 x∉Lx∈/L则无论证书如何伪造验证器至少以某个常数概率拒绝。形式化地PCP定理Arora-Safra, 1992; Arora-Lund-Motwani-Sudan-Szegedy, 1998断言NPPCP(O(log⁡n),O(1))NPPCP(O(logn),O(1))这个等式表示NP中的任意语言都有一个概率可验证的证明系统其中验证器使用 O(log⁡n)O(logn) 个随机比特即从多项式大小的证书中随机选择位置查询证书的 O(1)O(1) 个比特然后根据这些常数个比特的值立即决定接受或拒绝。如果 x∈Lx∈L存在证书使接受概率为1完备性如果 x∉Lx∈/L对任意证书接受概率 ≤1/2≤1/2可靠性。这一定理是计算复杂性理论的里程碑。它等价于说任何NP问题的证书可以被重新编码为一种“鲁棒”的格式——即使验证器只窥视其中常数个位置任何欺骗企图都会以常数概率被发现。常数查询意味着验证器的检查是极其局部的对数随机比特意味着验证器的随机选择空间仅为多项式大小。二、PCP定理的直观意义从全局验证到局部验证为理解PCP定理为何如此重要不妨将其与经典的NP证书验证做个对比。经典场景老师批改一份数学试卷。要判断试卷是否正确老师必须逐行检查每一步推导——这相当于阅读整个证书。PCP场景老师被允许随机抽取试卷中的三个位置比如第1行第3个等号右侧、第7行第5个符号、第15行第2个变量仅根据这三个位置的值就能以极高的置信度判断整份试卷是否正确。如果试卷确实正确老师总是接受如果试卷有错无论学生如何精心伪造老师至少有一半概率发现错误。PCP定理断言任何数学证明都可以被重新格式化为一种“鲁棒编码”——比如将证明写成一叠纸牌错误会被扩散到整叠牌中以至于任何错误都必然导致随机抽牌时暴露出矛盾。这种编码的存在性是PCP定理最深层的魔法。三、间隙放大与不可近似性的导出机制PCP定理如何与近似难度产生关联答案在于间隙放大技术。考虑最大3-SAT问题的优化版本给定一个3-CNF公式目标是找到一组赋值使得被满足的子句数量最大。判定版本的3-SAT问的是“是否所有子句都能被满足”。PCP定理提供一个更精细的刻画将一个NP完全的判定问题归约到一个“间隙”版本的3-SAT——要么所有子句都可满足要么任何赋值至多满足其中 1−ε1−ε 比例的子句εε 是某个常数。判定这两种情形哪一成立仍然是NP完全的。形式化地存在常数 ε0ε0使得以下问题是NP难的给定一个3-CNF公式 φφ区分以下两种情况是实例OPT(φ)1OPT(φ)1所有子句均可满足。否实例OPT(φ)≤1−εOPT(φ)≤1−ε任何赋值至多满足 (1−ε)(1−ε) 比例的子句。这一“间隙”直接给出了最大3-SAT的不可近似性若存在一个近似比严格小于 1/(1−ε)1/(1−ε) 的多项式时间近似算法则可以用它来区分上述两种情况在是实例上输出 ≥(1−ε)×≥(1−ε)× 近似比在否实例上输出 ≤1−ε≤1−ε从而在多项式时间内判定NP完全问题。因此在P≠NP假设下最大3-SAT不存在近似比优于 1/(1−ε)1/(1−ε) 的多项式时间近似算法。通过优化PCP构造的参数减小查询数、降低可靠性误差Håstad在2001年将这一间隙推向极致对于任意 δ0δ0区分满足全部子句的公式与至多满足 7/8δ7/8δ 比例子句的公式是NP难的。而随机赋值期望满足 7/87/8 的子句——这是平凡的 7/87/8 近似算法。由此得到最大3-SAT的近似比下界为 7/8δ7/8δ对任意 δ0δ0匹配平凡随机算法的 7/87/8 上界。换言之对于最大3-SAT随机赋值已经是最优近似——不能做得更好。四、团问题的不可近似性PCP定理在团问题上的应用同样震人心魄。回忆第42篇团问题是NP完全的。但它的近似难度远比“精确求解困难”更为严峻。将PCP的验证过程映射为图结构顶点对应于验证器的所有随机选择及其在该随机选择下接受的所有可能证书局部视图。边连接相容的两个局部视图。由此构造的图中大小为图中顶点总数某个比例的团对应于一个使验证器以高概率接受的全局证书。通过这一构造PCP定理导出了以下结果存在常数 ρ1ρ1使得将团的大小近似到 ρρ 倍以内是NP困难的。随后的一系列改进不断推高这个下界。Feige等人在1996年证明若NP ⊈⊆ ZPTIME(npolylog nnpolylog n)则团的大小无法在 n1−εn1−ε 因子内近似对任意 ε0ε0。Håstad在1999年进一步将下界推到 n1−εn1−ε随后Zuckerman、Khot等人将之推进到 n/2(log⁡n)3/4εn/2(logn)3/4ε 甚至几乎匹配的 n1−o(1)n1−o(1) 下界。这些结果意味着团问题不仅是NP完全的——它在近似意义下是“最硬的”NP问题之一。不仅找不到精确解连有意义的近似都遥不可及。对于一个已知包含一个大小为 n/2n/2 的团的图多项式时间算法甚至无法找到一个大小为 n0.99n0.99 的团——任意常数因子近似都会导致PNP。团问题的不可近似性与顶点覆盖形成了鲜明对比。顶点覆盖存在简单的2-近似算法且在某些假设下2是最优的。两个在图论上通过补图操作对偶的问题在近似难度上却有着天壤之别——顶点覆盖属于APX类存在常数近似团问题则属于“极难近似”的类。这也再次说明了图论结构上的微小差异可能对应着计算复杂度的巨大鸿沟。五、不可近似性结果的全景PCP定理及其后续发展为大量经典优化问题划定了近似的理论极限。集合覆盖Feige在1998年证明若P≠NP集合覆盖不存在 (1−ε)ln⁡n(1−ε)lnn 的近似算法。这与第24篇和第27篇给出的 O(log⁡n)O(logn) 贪心近似相匹配——贪心算法在近似比意义上已是最优。最大团与最大独立集如前述不可近似到 n1−εn1−ε 因子以内。旅行商问题一般图若边权无三角不等式约束旅行商问题不可近似到任意常数因子以内见第20篇。度量旅行商问题存在 3/23/2 的近似算法Christofides而Papadimitriou-Vempala和Karpinski-Lampis等人证明在某些限制下逼近至 1.0041.004 以内仍是NP困难的。图着色三着色是NP完全的。对于一般图Garey和Johnson证明若存在一个近似比小于 4/34/3 的多项式时间近似算法则PNP。更惊人的是对于任意常数 ε0ε0在 nεnε 因子内近似色数是NP困难的。背包问题背包问题存在FPTAS因此它可以被近似到任意接近最优。第28篇的分析表明FPTAS的存在性与问题非强NP完全性密切相关。这些结果共同描绘了一幅精细的近似难度地图不同问题的近似难度从“任意精度可近似”FPTAS到“常数近似”APX类到“对数因子近似”集合覆盖到“多项式因子不可近似”团问题形成了一个层级分明的谱系。六、总结与展望PCP定理将NP的证书验证从全局检查转化为局部随机抽查由此导出的间隙放大技术为不可近似性理论提供了统一的方法论框架。从最大3-SAT的 7/87/8 到团问题的 n1−εn1−ε不可近似性下界证明了这些问题的近似难度是内禀的——它们不因算法设计技巧的缺乏而无法逼近而是问题结构本身就排斥高效的近似方案。不可近似性理论与第20篇的近似算法设计共同构成了现代近似算法的双翼。前者划定了“不能做什么”的理论极限后者展示了“能做到什么”的构造方法。算法的设计空间恰好在这两条边界之间展开——知道下界让研究者不必徒劳地追求不可能实现的近似比而将精力集中在仍有改进空间的区域。PCP定理的思想也深刻影响了后续的理论发展。下一篇我们将进入参数化复杂度的深化——固定参数与超越NP的算法设计范式。参数化算法将“困难”集中在小参数上而不可近似性则将“困难”锁定在近似比上。两者的交集——参数化近似算法——是当前理论计算机科学最活跃的前沿之一。