NP 是 Non-deterministic Polynomial 的缩写,  NP 问题通俗来说是其解的正确性能够被很容易检查的问题, 这里"很容易检查"指的是存在一个多项式检查算法.

例如, 著名的推销员旅行问题(Travel Saleman Problem or TSP):  假设一个推销员需要从香港出发, 经过广州, 北京, 上海,  ....., 等 n 个城市， 最后返回香港。 任意两个城市之间都有飞机直达， 但票价不等。现在假设公司只给报销 $C 块钱, 问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 $C ?

推销员旅行问题显然是 NP 的. 因为如果你任意给出一个行程安排, 可以很容易算出旅行总开销. 但是, 要想知道一条总路费小于 $C 的行程是否存在, 在最坏情况下, 必须检查所有可能的旅行安排! 这将是个天文数字.

NP-complete 问题是所有 NP 问题中最难的问题. 它的定义是, 如果你可以找到一个解决某个 NP-complete 问题的多项式算法, 那么所有的 NP 问题都将可以很容易地解决.

通常证明一个问题 A 是 NP-complete 需要两步, 第一先证明 A 是 NP 的, 即满足容易被检查这个性质; 第二步是构造一个从某个已知的 NP-complete 问题 B 到 A 的多项式变换, 使得如果 B 能够被容易地求解, A 也能被容易地 解决. 这样一来, 我们至少需要知道一个 NP-complete 问题.

第一个 NP complete 问题是 SAT 问题, 由 COOK 在 1971 年证明. SAT 问题指的是, 给定一个包含 n 个布尔变量(只能为真或假) X1, X2, .., Xn 的逻辑析取范式, 是否存在它们的一个取值组合, 使得该析取范式被满足? 可以用一个具体例子来说明这一问题, 假设你要安排一个 1000 人的晚宴, 每桌 10 人, 共 100 桌. 主人给了你一张纸, 上面写明其中哪些 人因为 江湖恩怨不能坐在同一张桌子上, 问是否存在一个满足所有这些约束条件的晚宴安排? 这个问题显然是 NP 的, 因为如果有人建议一个安排方式, 你可以很容易检查它是否满足所有约束. COOK 证明了这个问题是 NP-complete 的, 即如果你有一个好的方法能解决晚宴安排问题, 那你就能解决所有的 NP 问题.

这听起来很困难, 因为你必须面对所有的 NP 问题, 而且现在你并不知道任何的 NP-complete 问题可以利用.  COOK 用非确定性图灵机( Non-deterministic Turing Machine ) 巧妙地解决了这一问题.

正式地, NP 问题是用非确定性图灵机来定义的, 即所有可以被非确定性图灵机在多项式时间内解决的问题. 非确定性图灵机是一个特殊的图灵机, 它的定义抓住了"解容易被检查" 这一特性. 非确定性图灵机有一个"具有魔力的"猜想部件, 只要问题有一个解, 它一定可以猜中. 例如, 只要存在哪怕一个满足约束的晚宴安排方式, 或是一个满足旅行预算的行程安排, 都无法逃过它的法眼, 它可以在瞬间猜中. 在猜出这个解以后,  检查确认部分和一台普通的确定性图灵机完全相同,  也即是等价于任何一个实际的计算机程序.

COOK 证明了,  任意一个非确定性图灵机的计算过程,  即先猜想再验证的过程, 都可以被描述成一个 SAT 问题,  这个 SAT 问题实际上总结了该非确定性图灵机在计算过程中必须满足的所有约束条件的总和(包括状态转移, 数据读写的方式等等), 这样, 如果你有一个能解决该 SAT 问题的好的算法, 你就可以解决相应的那个非确定性图灵机计算问题, 因为每个 NP 问题都不过是一个非确定性图灵机计算问题, 所以, 如果你可以解决 SAT , 你就可以解决所有 NP 问题. 因此, SAT 是一个 NP-complete 问题.
 
有了一个 NP-complete 问题, 剩下的就好办了, 我们不用每次都要和非确定性图灵机打交道, 而可以用前面介绍的两步走的方法证明其它的 NP-complete 问题. 迄今为止, 人们已经发现了成千上万的  NP-complete 问题, 它们都具有容易被检查的性质, 包括前面介绍的推销员旅行问题. 当然更重要的是, 它们是否也容易被求解, 这就是著名的 P vs NP 的问题.

图灵机第一次给出了"计算"的精确定义.  所有可计算的都是被图灵机可计算的, 同样, 不可计算的指的是不可被图灵机计算的.

利用图灵机这个计算模型, 第一个可以得到的结论就是存在不可计算的数(incomputable numbers). 我们说一个数  r 是可计算的, 如果存在一台图灵机 M 使得 r 是 M 的输出结果. 证明很简单, 因为图灵机是可数无穷的, 我们可以把所有图灵机编号, M1, M2, ...., 它们所计算的数记为 r1, r2, .... 而实数是不可数无穷, 所以一定存在不可计算的数. 简单地说, 我们没有足够多的图灵机来计算所有的数!

关于图灵机的另一个重要结论是图灵机停机问题(The Halting Problem)的不可判定性. 图灵机停机问题: 能否给出一个判断任意一个图灵机是否停机的一般方法? 答案是 NO, 不可能.

这个问题实际上是问: 是否存在一台"万能的"图灵机 H, 把任意一台图灵机 M 输入给 H, 它都能判定 M 最终是否停机, 输出一个明确的 "yes" 或 "no" 的答案? 可以利用反证法来证明这样的 H 不可能存在.  假定存在一个能够判定任意一台图灵机是否停机的万能图灵机 H(M),  如果 M 最终停机, H 输出 "halt"; 如果  M 不停机,  H 输出 "loop". 我们把 H 当作子程序, 构造如下程序 P:

function P(M) {

  if (H(M)=="loop")   return "halt";

  else if (H(M)=="halt")  while(true); // loop forever

}

 因为 P 本身也是一台图灵机, 可以表示为一个字符串, 所以我们可以把 P 输入给它自己, 然后问 P(P) 是否停机. 按照程序 P 的流程, 如果 P 不停机无限循环, 那么它就停机, 输出"halt"; 如果 P 停机, 那么它就无限循环, 不停机; 这样无论如何我们都将得到一个矛盾, 所以假设前提不成立, 即不存在这样的 H. 或者说, 图灵机停机问题是不可判定的(undecidable).

1936 年, 图灵发表了著名的论文"On Computable Numbers, with an Application to the Entscheidungsproblem " , 提出了图灵机的定义,  并开启了一个新时代.

图灵机 M 是一个抽象的数学模型, 它包含如下部分:

(1) 一系列有限的状态, 任一时刻 M 只能位于其中的一个状态; 其中有四个特殊的状态: 起始状态, halt(停机状态), yes(接受状态),  和 no(拒绝状态); 后三种都是结束状态, 一旦 M 进入这些状态, 则计算停止.

(2) 一条无限长的纸带, 分为一个个方格, 每个方格可以写一个字符, 0  或 1, 或者为空; 纸带有一个特殊的位置作为起始位置;

(3) 一个读写头, 它可以扫描纸带当前方格的内容, 也可以改写当前方格的内容, 还可以向左移动一格, 或者向右移动一格;

(4) 一个控制单元, 它是一系列按顺序执行的指令, 规定了 M 在当前状态下和读取当前的纸带内容后, 下一个状态是什么以及要做什么样的动作; 可以作的动作包括: 改写纸带当前方格, 左移一格, 右移一格, 或不动.

以上描述的图灵机进行一次计算的过程如下:

在最开始,  M 处于起始状态, 纸带上紧靠起始位置的左侧有一段连续的有限长度的字符串, 表示计算的输入, 其它方格为空, 开始时读写头位于起始位置.  从这个起始状态开始,  M 按照它的控制程序逐条执行,  根据当前状态和读入的内容,  改变状态, 打印字符, 移动读写头; 然后执行下一条指令; 然后再下一条; ........ 最后,   M 如果停机, 将会停在以下三者之一: "停机状态",  " yes(接受状态)",  或 "no(拒绝状态)".

假设输入为 x, 如果 M 停在"停机状态",  则纸带上起始位置右段的字符串 y 就是输出结果, 记为  M(x) = y; 如果 M 停在 "yes" 状态, 则记 M(x) = yes, 此时我们说 M 接受了 x;  如果 M 停在 "no" 状态, 则记 M(x) = no, 此时我们说 M 拒绝了 x.

当然, 对于输入 x, M 也可能永远不停机.

上面描述的图灵机更准确地应该称为决定型图灵机(Deterministic Turing Machine), 因为它的每一步都由当前 状态和当前输入明确决定, 不包含任何不确定性.  图灵机是计算机的抽象模型, 其中纸带相当于存储器, 读写头相当于读写装置, 指令集合相当于程序, 图灵机不停机相当于程序进入死循环. 图灵机也描述了人脑在进行数学计算时的抽象思维过程.

图灵机对计算(computation)和算法(algorithm)给出了一个明确的定义.  凡是可计算的, 都可以用图灵机来计算.   在此基础上,  图灵还证明了不可计算的数的存在, 以及图灵机停机(The Halting Problem)问题的不可判定性,  而这一切, 又都是为着回答另一个更大的问题, 即希尔伯特(Hilbert)提出的  Entscheidungsproblem 问题. 即能否找到一个通用方法(即算法或图灵机)来判定任一个给定的数学命题是真是假.  图灵机停机问题的不可判定性对此给出了断然的否定答案.  随后我们再来仔细看看上述这些问题到底是怎么回事.

可计算性(computability)理论关心的是哪些问题(problem)可以用计算机求解(computable)?  哪些不能 ? 计算复杂性(complexity)关心的是哪些问题能够用计算机快速地解决(efficiently computable)? 哪些不能被计算机快速解决?

  这自然要先涉及到以下基本问题: 什么是一个 problem ? 什么是 computation ?  怎样才算是解决了一个问题?  怎么度量一个问题的复杂度? 等等. 当然, 最基本的问题是, 什么是一个计算机?

在真正的计算机诞生之前, 1936 年, 英国的数学家 图灵(Alan Turing)提出了一个叫  图灵机(turing machine)的计算模型, 它实际上是人脑的计算过程的一个抽象模型.

 任何一台计算机(笔记本或是大型机), 任何一种编程语言(Java or C++), 本质上都是一个图灵机.  著名的 丘奇-图灵假想(Church-Turing thesis) 指出:

一切可计算的, 都可以被图灵机计算

Everything computable is computable by a Turing machine.

这不是一个可以证明的定理, 而是一个假想. 但是, 迄今为止人们所能想到的任何计算模型, 都被证明是与图灵机等价的. 根据这一论断, 人们把 " 可计算的(computable)" 定义为 " 可以被一个图灵机计算的(computable by a Turing machine) " .  这是一个简单而美丽的定义, 解决了长期以来令数学家们头疼的" effective computation" 的定义问题.