<读书笔记> 什么是P问题、NP问题和NPC问题

2024-02-19

该文章转载自http://www.matrix67.com/blog/archives/105。

什么是P问题、NP问题和NPC问题

  • 时间复杂度

时间复杂度可以简易地分为两个类别。第一个类别包括O(1)、O(log(n))、O(n^a)等，我们称其为多项式级别地复杂度，因为它的规模n出现在底数的位置；第二类则包括O(a^n)和O(n!)，计算机往往无法承受此类复杂度。它是非多项式级的，需要的时间太多，往往会超时，除非是数据规模非常小。

  • 不可解问题

自然地，人们会想到一个问题：会不会所有的问题都可以找到复杂度为多项式级的算法呢？很遗憾，答案是否定的。有些问题甚至根本不可能找到一个正确的算法，称之为“不可解问题”（Undecidable Decision Problem）。常见的不可解问题如The Halting Problem。

  • P问题

那如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。

  • NP问题

这里需要强调的是：NP问题并不是非P类问题。NP问题指的是可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式时间里猜出一个解的问题。找一个解很难，但验证一个解很容易。比如在Hamilton问题中，给你一个图，问你能够找到一条经过每个顶点一次且恰好一次最后又走回来的路（Hamilton回路）。这个问题目前还没有找到多项式级别的算法，但是要验证一条路是否恰好经过了每一个顶点是很容易的。之所以要定义NP问题，是因为通常只有NP问题才可能找到多项式的算法。当一个解都不能在多项式时间内验证时，要在多项式时间内解决这个问题是很困难的。

很显然，所有P问题都是NP问题。能多项式地解决一个问题，必然能多项式地验证一个问题的解。但所有NP问题都是P问题吗？这便是经典的千禧问题“P=NP？”。大部分人认为，这是并不成立的，也就是说，存在至少一个不可能有多项式级复杂度的算法的NP问题。

  • NPC问题

人们如此坚信P≠NP问题是有原因的，在研究NP问题的过程中找出了一类非常特殊的NP问题，称之为NPC问题。

在说明NPC问题前，先引入一个概念-规约（reducibility）。简单地说，一个问题A可以约化成问题B的含义即是，可以用问题B的解法解决问题A，或者说，问题A可以“变成”问题B。如Hamilton回路可以约化成TSP问题：在Hamilton回路问题中，两点相连即这两点距离为0，两点不直接相连则令其距离为1，于是问题转化为在TSP问题中，是否存在一条长为0的路径。Hamilton回路存在当且仅当TSP问题中存在长为0的回路。

问题A可以约化成问题B有一个重要的直观意义：B的时间复杂度高于或者等于A的时间复杂度。也就是说，问题A不比问题B难，因为问题A是可以通过问题B进行解决的。

显然，约化是具有传递性的。如果A可以约化成B，B可以约化成C，那么显然A也可以约化成C。

需要注意的是，这里的可约化是指可多项式地约化（polynomial-time reducible），即变换输入的方法是能在多项式时间里完成的。

因此，通过约化，问题的时间复杂度不断提升，是否能找到一个能“通吃若干个小NP问题的一个稍复杂的大NP问题，那么最后是否能找到一个通吃所有NP问题的超级NP问题”？答案是肯定的。

这就是NPC问题。它不只一个，而是很多个，它是一类问题。NPC问题的定义为：同时满足 是一个NP问题 和 所有的NP问题都可以约化到它 两个条件的问题就是NPC问题。

因此，要证明一个问题是NPC问题也很简单，首先证明它至少是一个NP问题，然后再证明其中一个已知的NPC问题可以约化到它。

既然所有的NP问题都能约化成NPC问题，那么只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP也就等于P了。但目前还没有找到NPC问题的多项式有效算法。

  • NP-hard问题

NP-hard问题则是另一类问题，它满足NPC问题定义的第二条但不一定要满足第一条问题。也就是说，只要所有的NP问题都可以约化到该问题，该问题甚至可以是多项式时间内无法验证解的，那它就是NP-hard问题。因此，NPC问题也是一类NP-hard问题。