NP猜想（二） (3-2)

这个证明太显然了。要验证某个SAT问题，只需要把任意给定的n个逻辑变量的取值带入那个逻辑表达式运算一下，看结果是否为真即可。因为逻辑表达式都是基于“与、或、非”这几种运算的，这个运算过程必然是在以n为变量的多项式步骤内可以完成的。

（2）难的是这第二步，要证明任意一个NP类问题都可以在多项式时间复杂度内规约为SAT问题。

这个证明最主要难在如何处理“任意”这个条件。NP类问题无穷多种，它们唯一的共同点就是给出一个待定解，可以在多项式时间复杂度内判断是否真的是这个问题的解。库克的论文中给出了一个非常巧妙的思路，充分利用这个唯一的共同点，基于非确定图灵机的模型及其运行过程，完成对一个逻辑表达式的构造。而这个构造出来的逻辑表达式对应的SAT问题，就是被规约到的问题。

（I）对于任意一个NP类问题，既然都可以在多项式时间复杂度内完成对某个待定解的判定，那么对应这个待定解，也必然存在着一个相应的图灵机来完成这个判定过程，且这个图灵机的运行时间复杂度是多项式级的。既然该问题的每个待定解都对应着一个图灵机的判定过程，那么也就意味着存在一个非确定图灵机（NDTM），对于每个待定解，这个NDTM都存在着某个运行分支可以完成相应的判定过程。特别地，对于每个真正的解，相应的NDTM运行分支一定会给出“接受”的结果。

（II）由于对任意一个NP类问题，相应的NDTM是确定的，显然其控制规则TABLE也是确定的。而且，对于NDTM的每个运行分支，都有一条确定的运行路径。

我们假设类似上图的TABLE表中有t行状态，分别为{Q0, Q1, Q2, ......, Qt}，我们设第i步的状态为 qᵢ {Q0, Q1, Q2, ......, Qt}；又因为这个NDTM至多运行P(n)步（P(n)是n的某个多项式函数），因此至多纸带上有P(n)+1个格子被读写，于是我们设初始输入为 S₀ ，第i步的时候纸带上的字符集合为 Sᵢ ，这里每个 Sᵢ 的长度都是P(n)+1 。

于是，NDTM的每个运行分支都会形成一组确定的（ qᵢ，Sᵢ ）序列。如果序列的最后一个 qᴘ₍ₙ₎₊₁ 状态是“Accept”，就说明输入 S₀ 是这个NP类问题的解。

（III）核心步骤到了：如果某个输入 S₀ 是那个NP类问题的解，就意味着至少存在一个按照上述定义确定的、符合这个NDTM运行逻辑规则的（ qᵢ，Sᵢ ）序列，且其 qᴘ₍ₙ₎₊₁ 状态是“Accept”；反过来，如果我能找到一个按照上述定义确定的、符合这个NDTM运行逻辑规则的（ qᵢ，Sᵢ ）序列，且其 qᴘ₍ₙ₎₊₁ 状态是“Accept”，那么这组序列的初始输入 S₀ 就必然是那个NP类问题的解。

剩下的事就是构造一个逻辑表达式，使得这个逻辑表达式得到满足的时候，就对应着一个符合这个NDTM运行规则的（ qᵢ，Sᵢ ）序列，且其 qᴘ₍ₙ₎₊₁ 状态是“Accept”。由于图灵机运行规则的确定性，这个逻辑表达式显然存在，且其构造不能用“难”来形容，而应该用“复杂”来形容，需要细致、认真、准确的态度和基本的逻辑能力。本文就不赘述了，有兴趣的可以参看相应专业的参考书。

（IV）既然我们构造出了一个逻辑表达式，一旦这个逻辑表达式被满足了（这正好是一个SAT问题），就意味着那个NP类问题有解了，那么显然那个NP类问题已经被规约到了一个SAT问题。而且，构造过程其实就是NDTM这个分支的运行过程，其时间复杂度当然是多项式级别的。由此，库克证明了任意NP类问题都可以在多项式时间复杂度内规约为一个SAT问题。

三、其它已经发现的NPC问题

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。