引言

在前面的章节中,我们解决了不同复杂性的问题。一些算法具有较低的增长率,而另一些具有较高的增长率。增长率低的问题被称为简单问题(或易于解决的问题),而增长率高的问题被称为难题(或难以解决的问题)。这种分类是根据算法解决问题的运行时间(或内存)来进行的。

时间复杂度 数量级 例子 问题类别
O(1)O(1) 常数阶 将元素插入链表头部 易于解决的问题
O(logn)O(logn) 对数阶 在二叉搜索树中搜索元素 易于解决的问题
O(n)O(n) 线性阶 在无序数组中查找元素 易于解决的问题
O(nlogn)O(nlogn) 线性对数阶 归并排序 易于解决的问题
O(n2)O(n^2) 平方阶 图中两个顶点的最短路径 易于解决的问题
O(n3)O(n^3) 立方阶 矩阵相乘 易于解决的问题
O(2n)O(2^n) 指数阶 汉诺塔问题 难以解决的问题
O(n!)O(n!) 阶乘阶 字符串排列 难以解决的问题

有许多我们并不知道如何求解的问题。到目前为止,我们所看到的所有问题都是那些可以通过计算机在确定性时间内解决的问题。在开始本章的讨论之前,让我们看看本章中需要使用到的基本术语。

在计算机科学中,为了理解不存在解决方案的问题,将问题分为不同的类,我们称之为复杂性类(complexity class)。在复杂性理论中,复杂性类是一组与复杂性有关的问题。它是计算理论的一个分支,主要研究为了求解一个给定问题的计算过程中所需的资源。

最常见的资源有时间(算法需要花费多少时间代价来解决问题)和空间(算法需要花费多少内存代价来解决问题)。

复杂性类的类型

P类

P类问题是可以用多项式时间求解的确定性机器来求解的一组判定性问题(P代表多项式时间)。P类问题是一组容易找到解决方案的问题。

代表:排序、图的连通性、最短路径等问题。

NP类

NP(代表非确定性多项式时间)类问题是可以通过多项式时间的非确定性机器求解的一组判定性问题。NP类问题是指一组难以找到解决方案但易于验证的问题。这意味着,如果有人解决了NP类问题,我们可以在多项式时间内告诉他这个问题是否正确。

代表:旅行商问题(TSP)、布尔可满足性问题(SAT)等。

Co-NP类问题

Co-NP问题是NP问题的补集,也就是与NP问题相反。如果Co-NP问题中的答案是否定的,那么这个事实就可以用多项式时间来检查。

P 可以在多项式时间内求解
NP 实例可以在多项式时间内验证
Co-NP 实例可以在多项式时间内验证

代表:全称可满足性问题(TAUT,是否所有的布尔公式都为真)等。

P类、NP类和Co-NP类的关系

P类问题也是NP类问题。如果一个问题是P类问题,那么我们可以在多项式时间内验证它的是实例。类似地,P类问题也是Co-NP类问题。

NP与P.drawio

计算机中一个很重要的开放性问题是证明是否P=NP。直观上P≠NP,但是没人知道怎么证明。另一个开放性问题是NP和Co-NP是否不同。即我们可以快速验证每个是实例,也不能认为我们同样可以快速验证某个否实例。一般认为NP≠Co-NP,但也没有人知道如何证明。

NP难类

NP中的每个问题都可以归约(后续会介绍)为NP难(NP-hard)问题。由于NP难问题可能不在NP中(即,可能没有多项式时间解法的问题),因此需要很长的时间才能验证他们。如果有人给出了NP难问题的解,我们需要很长的时间来验证给出的解是否正确。

如果K是NP难问题,那么蕴含着:如果K能够在多项式时间内被求解,则可证P=NP(因为所有的NP问题都可以被归结为NP难)。

NP与NP难

代表:包含很多的优化问题和决策问题,比如旅行商问题的优化版本、3-SAT等

NP完全类

最后,如果一个问题既是NP难问题和NP问题,那么该问题是NP完全(NP-complete/NPC)问题。NP完全问题是NP中最难的问题。如果有人能发现一个NP完全问题的多项式时间算法,那么就可以找到每个NP完全问题的多项式时间算法。

这意味着我们可以快速检查答案,并且NP中的每个问题都可以归约到该问题。

NPC问题

代表:经典的NP完全问题包括3-SAT、顶点覆盖问题(Vertex Cover)、哈密顿回路问题(Hamiltonian Circuit)等。

NPC和NP难的关系

  • NP难问题至少和NPC问题一样难。
  • NPC问题肯定是NP难的,但是反之不一定

因为NPC问题虽然目前无法在多项式时间内给出解法,但是可以在多项式时间内验证解的正确性;而NP难问题则可能无法保证能在多项式时间内验证解。

各类关系

我们可以总结出P类、NP类、Co-NP类、NP难类和NP完全类的关系,如图所示(请注意这些目前还只是一个假设):

各类关系

NP难问题是NP完全问题的严格超集(superset)。一些问题(如停机问题)是NP难问题,但不是NP问题。一般而言,NP难问题可能无法解决。我们可以给出NP难问题和NP完全问题困难性之间的不同,因为NP类包含了所有比“最棘手”问题更容易的事情——如果一个问题不在NP中,那么该问题比NP中的所有问题都要困难。

P==NP吗?

美国麻省的Clay数学研究所于2000年5月24日在巴黎法兰西学院宣布:对七个“千年数学难题”中的每一个均悬赏100万美元,而问题NP =?P位列其首:

  1. P问题对NP问题
  2. 霍奇猜想
  3. 庞加莱猜想(2002.11-2003.7,俄罗斯数学家佩雷尔曼在3篇论文预印本中证明了几何化猜想,2006被授予菲尔兹奖)
  4. 黎曼假设
  5. 杨-米尔斯存在性和质量缺口
  6. 纳维叶-斯托克斯方程的存在性与光滑性
  7. 贝赫和斯维讷通-戴尔猜想

如果P=NP,这意味着每个可以被快速验证的问题都可以被快速解决。

这是一个世界性难题,目前没有人知道答案,因为现在没有人能证明P是否等于NP。许多NP完全问题至今还没有找到快速的解决方法。如果P=NP,那么就意味着有办法在多项式时间内解决这些NP完全问题。“快速”意味着解决这些问题不需要试错法。目前,求解这些问题可能需要数百万年,而未来的计算机可能将这数百万年的计算时间缩短到几分钟以内。

归约

假如我们想解问题X,但是X又非常复杂。这时候,我们想到有类似X的问题(假设为问题Y),那么我们可以尝试把X映射成Y,并通过解决Y来解决X。这个过程被称为归约

我们需要一些算法将问题X映射到问题Y,这可能需要花费线性或者更多的时间。基于这一点,解决问题X的成本可以表达如下:

解决X的成本=解决Y的成本+归约的时间解决X的成本=解决Y的成本+归约的时间

有时候我们可能需要多次调用使用Y的算法去解决问题X,则此时X的成本可以表示为:

解决X的成本=调用次数×解决Y的成本+归约的时间解决X的成本=调用次数\times 解决Y的成本 + 归约的时间

NP完全问题涉及的主要问题就是归约。这意味着,我们可以将给定的NP完全问题归约为其他已知的归约完全问题。由于NP完全问题很难被解决,并且为了证明给定的NP完全问题是困难的,我们可以选择一个已知的难题(已经证明了难题的困难性),通过将给定问题映射到该难题上的方法证明给定问题的困难性。

将给定难题归约到已知难题并不是强制的。有时候,我们也会将已知难题归约到给定难题。


100852589_p0