计算机考研之数据结构：P 问题和 NP 问题

在算法的时间复杂度估算中，通常教材和题目中的估算结果包括：$O(1),O(\log n),O(\sqrt{n}),O(n),O(n\log n),O(n^2),O(n^3),O(\log \log n)$ 等，这些时间复杂度之间，存在如下定性的大小关系：
$$O(1)<O(\log \log n)<O(\log n)<O(\sqrt{n})<O(n)<O(n\log n)<O(n^2)<O(n^3)$$
其中， $O(\log \log n),O(\log n),O(\sqrt{n}),O(n),O(n\log n),O(n^2),O(n^3)$ 等称为多项式时间复杂度（Polynomial Time Complexity），可以统一表示为 $O(f(n))$ ，且 $f(n)$ 为多项式。

如果从纯粹应付考试的角度来讲，知道上述内容就足够了。但是，如果作为一个未来的开发者，不能将仅仅以“考什么学什么”来要求自己，特别是在基础知识复习的时候，务必要多了解一些。本文即是对一般辅导资料的补充。

在算法复杂度理论中，多项式级的运行时间往往被认为是可接受的。某问题若可以用多项式复杂度的算法求解，则称该问题是可有效求解的，或者易解的。这样的问题也称为 P 问题（P，即 Polynomial，多项式）。

除了 P 问题之外，还有另外一类问题，只能用指数时间复杂度（Exponential Time Complexity）的算法求解，称为 NP 问题（即 Non-deterministic Polynomial Problem，非确定多项式问题），例如，计算斐波那契数列的一种算法的时间复杂度就是指数时间复杂度，即 $T(n)=O(a^n),(a>1)$ 。一般认为，指数时间复杂度的算法无法真正应用于实际问题中，这类算法不是有效的算法。

P 问题

P 问题是指能够在多项式时间内解决的问题。这里的 “解决” 意味着存在一个算法，对于该问题的任何规模为 $n$ 的输入实例，都能在 $O(n^k)$ （ $k$ 为常数）的时间内给出正确的答案。

例如，判断一个整数是否为偶数就是一个 P 问题。我们可以设计一个简单的算法，只需要检查该整数的最后一位是否为 0、2、4、6 或 8，这个操作的时间复杂度为 $O(1)$ ，属于多项式时间复杂度。比如判断整数 1234，只看最后一位 4，就能在极短时间内得出它是偶数的结论。再如，计算两个矩阵的乘积也是一个 P 问题。通过标准的矩阵乘法算法，对于两个 $n\times n$ 的矩阵，其时间复杂度为 $O(n^3)$ ，同样在多项式时间内可解。像 $3\times 3$ 矩阵相乘，按照算法步骤就能在符合 $O(n^3)$ 时间复杂度的情况下得出结果。

计算一组数字的平均值也是 P 问题。假设有 $n$ 个数字，先将这 $n$ 个数字相加，时间复杂度为 $O(n)$ ，再除以 $n$ ，这一步时间复杂度为 $O(1)$ ，整体时间复杂度为 $O(n)$ ，属于多项式时间复杂度。例如有 5 个数字 1、2、3、4、5，相加操作执行 5 次，然后除以 5，很快就能得出平均值 3。

P 问题集合涵盖了大量我们日常遇到且能够有效解决的问题。这些问题可以通过现有的计算资源和算法，在合理的时间范围内得到解答。

NP 问题

NP 即非确定性多项式（non-deterministic polynomial）时间，NP 问题是指可以在多项式时间内通过非确定性算法验证其解是否正确的问题。这里的 “非确定性算法” 可以理解为在算法执行的某些步骤中，允许出现不确定的选择，并且如果一个问题存在至少一种可能的解能够在多项式时间内被验证，那么这个问题就属于 NP 问题。

一个经典的 NP 问题例子是 “子集和问题”。给定一个整数集合 $S$ 和一个目标整数 $t$ ，判断是否存在 $S$ 的一个子集，使得子集中所有元素的和等于 $t$ 。假设我们得到了一个声称是该问题解的子集 $S^{\prime }$ ，要验证这个解是否正确，只需要对 $S^{\prime }$ 中的元素进行求和，然后检查和是否等于 $t$ 。这个验证过程的时间复杂度与子集 $S^{\prime }$ 的大小成正比，对于给定的输入规模（集合 $S$ 的大小为 $n$ ），验证时间是多项式时间 $O(n)$ 。例如，集合 S = { 1 , 3 , 5 , 7 , 9 } S = \{1, 3, 5, 7, 9\} S={1,3,5,7,9} ，目标 $t=15$ ，若给出一个解子集 S ′ = { 1 , 5 , 9 } S' = \{1, 5, 9\} S′={1,5,9} ，我们将 $S^{\prime }$ 中元素相加 $1+5+9=15$ ，与 $t$ 相等，验证了该解正确，且这个验证过程很快，时间复杂度符合 $O(n)$ ，这里 $n$ 为子集 $S^{\prime }$ 的元素个数 3。然而，找到这个解本身可能并不容易，目前没有已知的多项式时间算法能够直接找出满足条件的子集。

另一个著名的 NP 问题是 “旅行商问题”。假设有一个旅行商需要访问 $n$ 个城市，每个城市之间都有一定的距离，旅行商需要找到一条最短的路径，使得他能够遍历所有城市且每个城市只访问一次并最终回到出发城市。如果给定一条路径，我们可以在多项式时间内计算出这条路径的总长度，从而验证它是否是最短路径的候选解。例如有 4 个城市 A、B、C、D，假设各城市间距离为：A 到 B 为 5，A 到 C 为 3，A 到 D 为 7，B 到 C 为 2，B 到 D 为 4，C 到 D 为 6。若给定一条路径 A - B - C - D - A，计算路径长度为 $5+2+6+7=20$ ，计算过程简单，时间复杂度低。但要从所有可能的路径组合中找到最短路径，计算量随着城市数量 $n$ 的增加而呈指数级增长，目前还没有找到多项式时间的求解算法。

“哈密顿回路问题” 也是 NP 问题。对于一个给定的图，判断是否存在一条路径，从某个顶点出发，不重复地经过图中每个顶点恰好一次，最后回到起始顶点。若给出一条声称满足条件的路径，验证这条路径是否真的遍历了所有顶点且不重复，只需要依次检查路径上的顶点，时间复杂度与路径长度成正比，属于多项式时间。例如在一个有 6 个顶点的图中，给定路径 $v_1-v_2-v_3-v_4-v_5-v_6-v_1$ ，逐个检查顶点是否符合要求，能快速完成验证，但要找到这样一条回路却非常困难，没有多项式时间算法。

P 问题与 NP 问题的关系

P 问题和 NP 问题之间的关系是计算机科学领域中一个尚未完全解决的重大问题，即 “P 是否等于 NP”。直观上看，P 问题集合是 NP 问题集合的一个子集，因为如果一个问题能够在多项式时间内被解决，那么它的解必然可以在多项式时间内被验证。也就是说，所有的 P 问题都是 NP 问题。然而，目前还不清楚是否所有的 NP 问题也都是 P 问题，即是否存在一个通用的方法，能够将所有 NP 问题在多项式时间内转化为 P 问题来求解。

如果 P = NP，那么这意味着许多目前被认为难以解决的问题（如旅行商问题、子集和问题等）实际上都存在多项式时间的求解算法，这将对计算机科学以及众多依赖计算的领域产生革命性的影响。但目前为止，尽管经过了大量的研究，还没有人能够证明 P = NP，同时也没有人能够证明 P ≠ NP。

多项式时间复杂度、P 问题和 NP 问题是计算机科学中理解算法效率和问题难度的关键概念。多项式时间复杂度为我们评估算法性能提供了重要依据，P 问题代表了可有效求解的问题类别，NP 问题则涵盖了那些解的验证相对容易但求解可能困难的问题。而 P 与 NP 之间的关系，作为计算机科学领域的核心未解之谜，持续吸引着众多研究者不断探索和研究。