如何理解P和NP问题

一、背景

2000 年，美国克莱数学研究所公布了世界七大数学难题，又称千禧年大奖难题，规定对每一难题的破解者颁发一百万美元的奖金，P与 NP 问题被列为七大世界数学难题之首。

NP 问题是随着计算复杂性理论的产生而出现的. 根据计算复杂性理论，所有科学问题按其解决时间可分为三大类：多项式类、指数类和不可解类。

二、什么是P和NP问题

P类问题： 所有可以在多项式时间内求解的判定问题构成P类问题，例如乘法、人名排序。

判定问题：判断是否有一种能够解决某一类问题的能行算法的研究课题。

NP类问题： 所有的非确定性多项式时间可解的判定问题构成NP类问题。例如车辆路径规划、TSP 等，NP问题最显著的两个特点：一是分布及每一步的并行性，二是任何NP问题都可以转化为是和否的问题，最根本的是验证多项式。

非确定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的，算法的验证阶段是确定性的，它验证猜测阶段给出解的正确性。

NP问题包括P问题，如果能快速地检验问题，是否代表有快速方法破解问题？

1. 问题变大时，困难度是怎么增加的；
2. P代表多项式时间（Polynomial），P类问题中解决问题的步数和时间可以依问题大小用多项式函数表达；NP代表非确定性多项式时间（Non deterministic Polynomial time），重点是多项式时间内做检查，即如果有无限台电脑，可以在同一时间检查所有可能的答案，就可以在多项式时间内找到正确的答案；
3. NP完全问题：NP中困难的部分，即任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，如果可以找到解决NP-complete问题的快速程序，就可以解决所有NP问题；
4. NP-hard：指所有NP问题都能在多项式时间复杂度内归约到的问题。
5. EXP（指数）类问题，例如下棋的最佳棋路、运算和检查都需要指数时间；Co-NP不容易检查正确答案，但很容易排除错误答案；

三、理解P和NP问题

首先，了解图灵机模型（TURing Machine-TM），图灵机可以看做是计算机读或写 0 1 时直接进行工作的不见，实际上它是一个抽象的理想计算模型。在计算的每一时刻，它都处于一个可以用表达式描述的状态，这个表达式里包含了图灵机当前的状态、读写头目前所读的数，读写头即将在目前位置写入的数，以及未来读写头的去向（转移方案）等信息。

P和NP也可以表述为 1：在确定性图灵机下能用多项式求解的问题就是P类问题，而在非确定性图灵机下能用多项式求解的问题就是NP问题；

• 确定性图灵机与现实中单CPU的计算机在功能上完全等价，只能进行串行思维，而不能同时并行工作，只存在一种状态转移方案；
• 非确定性图灵机只是一种理论模型，现实中是不存在的。它具有并行工作的能力，完成一件事，要分若干部进行，每一步有多个可能的选择。
• 确定性图灵机在每一步只能选择一个目标，若进行下去后不能达到目的，可返回到这一步，再试另外的目标；而对非确定性图灵机而言，它每一步可以同时选择这一步的所有目标，并行的同时计算下去。

1971 年，库克发现并证明了第一个 NP 完全问题( NPC) ，也就是可满足性问题，即任何 NP 问题都可以在多项式时间内按多项式的规模转化为对可满足性问题的求解。只要可满足性问题具有多项式时间算法，则所有 NP问题都具有多项式时间算法，具有这样特性的 NP 问题，称为 NP 完全问题。从此你只要证明任何一个已知的 NP 完全问题，能在

多项式内转化到你所论及的问题就足够了，因为多项式转化具有传递性。

对于某个问题，若任何一个 NP 问题都可在多项式时间内按多项式的规模转化为对该问题的求解，则称该问题为 NP-hard。

显然，若任何一个 NP-hard 问题有多项式时间算法，则所有NP 问题具有多项式时间算法。而 NP 完全问题则是：既是 NP-hard 同时又属于 NP 的问题。

随着第一个 NP 完全问题的发现和证明，兴起了对这类问题之间的多项式转化研究. 在教科书中通常将这种转化称为归约。注意理解多项式归约必须把握两个关键点2：一是转化本身所需的时间是多项式， 二是转化后对原问题计算规模的扩大，不超出多项式的范围。A 问题归约到 B 问题是指 B 问题更具有普适性，即 B 问题的解决方法相对于 A 问题更具有普适性。

P 和 NP 属计算机算法，算法问题的核心是复杂的思路，而不是数学理论和公式。:即使证明了 NP = P，也不意味着能得到任意 NP 问题的有效的多项式时间算法。从根本上解决 NP 问题的途径是，或者证明NP 等于 P，从而从理论上找到 NP 问题的多项式时间算法；或者证明 NP 不等于 P，从而，某些 NP 问题永远也不可能有多项式时间算法，以免白费时间精力。

1. 杜立智,符海东,张鸿,黄远林.P与NP问题研究[J].计算机技术与发展,2013,23(01):37-42. ↩︎
2. 杜立智,陈和平,符海东.NP完全问题研究及前景剖析[J].武汉工程大学学报,2015,37(10):73-78. ↩︎