计算复杂性问题

在众多可计算问题里，难度天差地别：有的几毫秒就解决，有的即使用上全世界的计算机也算不完。旅行商问题是经典的代表之一：

旅行商问题的难点在于，可能的路线数量会随城市数量呈阶乘级暴涨。若按访问顺序的全排列粗略估计，10 个城市约有 $10! = 3\,628\,800$ 种不同顺序；增加到 20 个城市，路线数量已大到难以想象；

下表给出一台每秒运算 $10^{6}$ 次的计算机，在不同增长量级下的大致运行时间，你可以直观感受增长速度的差异。

从表中可以看出，若计算量呈平方级增长时，即便输入规模较大，计算时间仍在可接受范围之内。但指数级（$2^n$）、阶乘级（$n!$）增长则完全不同：对 $2^n$ 而言，规模到 50 时已超过人类寿命量级；对 $n!$ 而言，规模到 20 时已远超人类文明的时间尺度，到 30 时则远超宇宙年龄。

因此，对旅行商这类阶乘级增长问题，穷举所有可能路径理论上可行，但实际上永远算不完。

度量计算复杂性

1965 年，通用电气公司的工程师 Hartmanis 和 Stearns 注意到：随着问题描述规模的增大，算法所需的时间和空间会发生怎样的变化——这可以用来度量算法的复杂性。他们在论文《On the Computational Complexity of Algorithms》中，提出用时间和空间来衡量算法的复杂性，并引入了复杂度类的概念。这项工作开辟出一个全新的研究领域，即计算复杂性理论（Computational Complexity Theory）。由于这一开创性贡献，两人于 1993 年共同获得图灵奖。

在理论计算机科学中，时间复杂度指的是：当输入规模增加时，图灵机完成计算所需基本步骤数量的增长速度；空间复杂度则指图灵机在计算过程中，纸带上所使用格子数量随输入规模增长的速度。严格地说，图灵机本身并没有物理时间的概念，“时间”这一说法并不十分准确。不过，当计算机被真正制造出来后，每一步计算都对应一定的物理过程。单个物理过程所耗费的时间极其微小，但当步骤数量非常庞大时，累积时间便会十分可观。因此，人们将“计算步骤的增长规模”与实际运行时间联系起来，沿用了时间复杂度这一说法。

现在，人们常用大写的 $O$ 来表示时间复杂度的渐近上界，用 $n$ 表示问题的规模。比如指数级时间复杂度可以表示为 $O(2^n)$。

如果某个算法的运行时间可以表示为 $O(n^k)$，其中 $k$ 为常数，例如 $O(n^2)$、$O(n^3)$ 等，那么就称该算法是在多项式时间（Polynomial Time）内完成的。通常认为，多项式时间算法在实际计算中是可行且高效的。

复杂性问题分类

有了上面的约定之后，我们再继续对计算问题分类。

如果一个问题存在能在多项式时间内求解的算法，那么它就属于 P 类问题。其中，P 来自英文 Polynomial（多项式）。常见的 P 类问题包括：排序（如快速排序、归并排序）、查找（如二分查找）、图论问题（如最短路径、最小生成树）以及基础数学计算（如最大公约数、整数运算）。这类问题的共同特点是，随着输入规模的增大，计算时间仅按多项式规律增长。

若一个问题的解可以在多项式时间内被验证，但不一定能在多项式时间内被直接求解，则称其属于 NP 类问题。这里的 NP 来自 Nondeterministic Polynomial（非确定性多项式）。所有 P 问题都可以在多项式时间求解，自然也可以在多项式时间验证，因此 P 是 NP 的子集，写作 $P \subseteq NP$。

需要说明的是，复杂性理论中的 P、NP 通常针对的是判定问题（答案为“是/否”）。以旅行商问题为例，其优化形式是“找最短路径”；对应的判定形式则是：“是否存在一条总长度不超过 $K$ 的巡回路径？”后者才是严格意义上的 NP 问题。典型的 NP 问题还包括布尔可满足性问题（SAT）、顶点覆盖等。这类问题往往求解困难，但验证相对容易：以旅行商的判定版本为例，从头寻找一条足够短的路径，需要在海量可能路径中搜索，复杂度迅速爆炸；但如果给定一条路径，只需在很短的时间内计算总长度，并与给定阈值比较，即可验证它是否满足要求。

在所有 NP 问题中，还有一类最“困难”的问题，由 Stephen Cook 于 1971 年在论文《The Complexity of Theorem-Proving Procedures》中提出，被称为 NP 完全问题（NP-Complete，NPC）。一个问题如果同时满足以下两个条件，便可称为 NP 完全问题：

• 属于 NP：问题的解可以在多项式时间内被验证；
• NP-hard（NP 难）：任何 NP 问题都可以通过多项式时间归约（reduction）转换成这个问题。

这里的“归约”，起源于数学，用于将一个问题“转换”为另一个问题，从而借助已知问题的解法来解决新问题。它是证明不同复杂度类之间关系的重要工具。Stephen Cook 基于归约证明了“布尔可满足性问题”（SAT）是首个 NP 完全问题。根据这一结论，如果存在一个确定性多项式时间算法可以解决 SAT，那么所有 NP 问题都可以在多项式时间内解决，即 $P = NP$。这便是业内著名的“P 与 NP 问题”。

P 与 NP 问题

1972 年，加州大学伯克利的理查德·卡普（Richard Karp）发表论文《组合问题的可约性》（Reducibility Among Combinatorial Problems），证明了 21 个经典计算问题都是 NP 完全问题（NPC）。此后，人们又陆续发现了大量 NP 完全问题，如广义数独、n 阶魔方的最优解、扫雷一致性问题等。如今，已知的 NP 完全问题已有数千个，广泛存在于工程、调度、规划和组合优化等领域。

到目前为止，人们还没有找到能够在多项式时间内解决 NP 完全问题的算法。在实际应用中，对于许多相关的优化问题，人们往往只能借助近似算法或启发式算法，在可接受的时间内寻找一个“足够好”的解。但需要注意，“没有找到”并不等于“已经证明不存在”。也许某种尚未发现的算法，真的能够在多项式时间内解决这些问题；也许未来还会出现“另一个图灵”，从根本上改变我们对“计算”的理解。

如果能证明 $P=NP$，这无疑将成为计算科学乃至人类文明史上的重大突破。从工程设计、物流调度到科学研究，许多需要耗费巨大计算资源的问题，都将变得容易求解。2000 年，克雷数学研究所（Clay Mathematics Institute）在法国巴黎召开“巴黎千年会议”（Paris Millennium Event），将 $P$ 与 $NP$ 问题列为 21 世纪七大数学难题之首^[1]，并承诺为每个难题的解决提供 100 万美元奖金，有人戏称其为“最难拿的 100 万美元”。

值得一提的是，七大难题中的庞加莱猜想已于 2003 年由俄罗斯数学家佩雷尔曼证明。2006 年，国际数学联盟（IMU）将菲尔茨奖授予他，但他拒绝领奖：

2010 年，克雷数学研究所又将百万美元的千禧年大奖授予他，相比菲尔茨奖，千禧年大奖可是实实在在的财富。佩雷尔曼再度拒绝。据前所长詹姆斯·卡尔森回忆，他不愿参加任何仪式，只在住所门后说：“我不需要任何东西，我已经拥有了我所希望的一切。”

如今的佩雷尔曼生活在圣彼得堡，远离学术圈和公众视野，过着极其简朴的生活。偶尔有人在街头遇见他，很难把眼前这位不修边幅（略显邋遢）的人，与那个解决了百年数学难题的世界顶尖数学家联系在一起。