NP猜想（二）

为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：

（1）一条无限长的纸带TAPE。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号“B”表示空白。纸带上的格子从左到右依次被编号为 0,1,2,... ，纸带的右端可以无限伸展。

（2）一个读写头HEAD。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。

（3）一套控制规则TABLE。根据当前机器所处的状态（相当于当前所执行的指令）以及当前读写头所指的格子上的符号来确定读写头下一步的动作，改变纸带当前格子里面的符号（如需要），并令机器进入一个新的状态（相当于确定下一步要执行的指令）。这个TABLE其实就是一套指令集，它在某种意义上就相当于我们今天计算机里面的程序。它至少包括以下内容：改写当前格子为某个符号、读写头向左或者向右移动一步、确定下一步执行的指令。

为了让大家更容易理解图灵机，举个例子吧。下图就是某个图灵机的一张控制规则TABLE，这个图灵机假设输入是只有“a”和“b”两种字符组成的字符串，它能够判断这个字符串是否是类似“aaabbb”形式的，也就是由同样数量连续个a和连续个b组成的字符串。在图灵机中，“B”表示“空”（Blank），如果后续状态是“Qaccept”或者“Qreject”，则分别表示运行结束且判断结果为“是”或“否”。

当前状态 读B 读a 读b

Q0（写B，右移，Q0) （写B，右移，Q1) （写b，右移，Qreject）

Q1（写B，左移，Q2） （写a，右移、Q1) （写b、右移、Q1）

Q2 （写B、左移、Qreject） （写a.左移Qreject） （写B、左移、Q3）

Q3（写B，左移，Qaccept） （写a，左移，Qreject） （写b，左移，Q4）

Q4 （写B，右移，Q0） （写a，左移，Q4） （写b、左移，Q4）

（4）一个状态寄存器。它用来保存图灵机当前所处的状态，也就是当前需要执行的指令（上图中的Q0～Q4）。

某一些指令运行完毕后，图灵机就进入了“停机状态”，这时纸带上的符号或者“Accept”、“Reject”状态就是本次运行的结果。

图灵设计的这样一台机器能模拟人类所能进行的任何计算过程。不考虑效率的前提下，今天人类的再高端的计算机的程序运算都可以通过图灵机实现。

2、非确定图灵机（NDTM，Non-Deterministic Turing Machine）

非确定图灵机与前面说的图灵机的区别在于，“控制规则TABLE”中的确定的下一步动作不是一个，而是多个。在实际运行过程中，NDTM会随机选择某一个动作继续运行下去，形成一个运行分支。因此，NDTM针对同一个输入，实际运行结果是不确定的。但是有一点需要明确，就是NDTM中不会产生矛盾，某一个输入如果某个分支给出的结果是“接受”，那么无论选择哪一条道路，最终的结果都不会是“拒绝”（这里我们没有排除某种分支下某个NDTM无限运行下去，永不停机的可能）。

3、库克定理证明思路

做了这么多铺垫，我们来开始说库克定理的证明思路。请大家千万别跳过这一部分，这是NPC问题存在的鼻祖式证明。

（1）按照NPC问题的定义，先要证明SAT问题是一个NP问题。

这个证明太显然了。要验证某个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问题

“SAT问题”是在1971年由库克发现的第一个NPC问题。在之后的1972年，理查德·卡普将这个想法往前推进，发表了他著名的论文“Reducibility Among Combinatorial Problems”，在里面提出并证明了21个NPC问题。这些被证明为NPC的问题都是比较有名的组合数学与图论等方面的问题，包括“0-1整数规划”、“集合覆盖”、“哈密顿循环”、“3-SAT”问题、“背包问题”、“三位匹配问题”等等。

其中“哈密顿循环”演化而成的比较著名的一个问题叫做“推销员问题”，是说某个推销员要走访n个城市，每两个城市之间的距离都给出了，推销员从某给定的城市出发，要求每个城市走访一次后再回到出发城市，那么怎么安排走访顺序使得总行程最短？

这个问题在n的多项式时间复杂度内目前是无法求解的。如果用最笨的穷举法，总共可能的顺序有(n-1)!种情况，每种情况还需要计算n-1次加法，其时间复杂度为O((n-1)*(n-1)!) = O(n!)。当然，经过优化，肯定存在更理想的算法，比如通过动态规划精确算法，可以达到的时间复杂度为O(n² · 2ⁿ )。

四、关于NP是否等于P

2010年8月6日，HP LAB的 Vinay Deolalikar 教授宣布证明了NP ≠ P ，在他的主页上证明过程已经公布（PDF格式共103页），但在8月15日，专家学者对论文的看法基本达成共识，那就是证明不能成立。

时至今日，还没有哪位学者能够给出确定性的结论，但是计算复杂度理论的学者普遍认为NP ≠ P 。

当然，从非证明的角度来看这个问题的话，存在那么多个NPC问题，只要有一个能够找到多项式时间复杂度的算法，那么NP=P就成立了，可是50多年下来，一个都没有找到，这也从反面说明了NP ≠ P 的可能性很大。

我还看到过更具情感色彩的观点。麻省理工学院的科学家Scott Aronson在一篇博文中提出了10个NP ≠ P 的理由，我把第9个理由的大致内容记述在这里：如果NP=P，那么“创造性的飞跃”将没有特殊价值，在解决问题与认可解决方案之间没有根本的隔阂，任何能欣赏交响乐的人都是莫扎特，每个能看懂一步一步的数学证明的人都是高斯，每个能认识到好的投资策略的人都是巴菲特。

也许正是由于NP=P会使这个世界太过于无趣，所以上帝不允许这样的事情发生。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。