P vs. NP 五十年：AI正在解决不可解问题 (7)

8 量子计算机的力量

随着摩尔定律的失效，计算机研究人员将目光转移到量子计算机的领域，这些年，量子计算机的研究和应用正在经历大幅的增长。谷歌、微软和IBM等大型科技公司，以及各种创业公司都在量子计算机方面投入大量资源进行研究。美国发起了国家级的量子计算研究计划，中国等其他国家也在纷纷效仿。

在2019年，谷歌宣布他们已经通过使用53个量子比特的量子计算机实现了“量子霸权”，解决了当前传统计算机无法解决的很多计算任务。虽然有很多人质疑这个说法，但是我们无疑的正在处于量子计算新时代的起点之上。尽管如此，我们距离能够跑起来Peter Shor的量子算法，以及拥有一台真正的量子计算机，还有相当远的距离。保守来说，我们还需要几万个量子位的距离需要攻克。通常来说，量子计算机可以被理解成是由比特表示的状态数的系统，比如53个量子比特计算机的2^53个状态。这可能说明，我们可以通过创建特别多的状态位，也就是使用量子计算来解决NP完全问题——也就是大力出奇迹。但不幸的是，目前我们无法证明量子计算机能够充分操控这些状态位，也就是不知道使用什么算法来解决NP完全问题，在这个角度上，这个问题已经超出了Grover的算法限制。

9 复杂性更新

自从2009年以来，我们在高效计算理论方面取得了一些重大的进展。虽然这些结果在解决P和NP方面没什么帮助，但是它们可能从一旁帮助理解相关的问题，并且启发后世的一些研究发展。

图同构

一些NP问题无法表征为P（有效可解）或NP完全问题（与Clique问题一样难的问题）。我们之前讨论过的最著名的整数因式分解仍然需要指数级的时间来求解。对于另一个这样的问题，也就是图同构问题，我们最近看到了一些戏剧性的进展。图同构问题是指，人们可否找到两个图在统一表示下完全相同。具体举例来说，就像在Facebook中，当我们给定了两组1000人，我们能否将他们映射到另一个组中，在那个新组中好友的关系不变。（小A和小B是好友，在另一群人中A’和B’也是好友）

这个图同构的问题在80年代中有了一些理论上的证明。在80年代，有人用交互式的方法证明了图同构问题不是NP完全的，而且它其实不是很困难，在一些实际的情况下，使用启发式的方法也能快速找到解决答案。尽管如此，我们仍然无法找到一个能够在所有场景中都快速找到解的算法。Laszlo Babai在2016年对该问题进行了深入研究，并发表了一种用于图同构的多项式时间的解决算法。简单来说，P中的问题在多项式时间内如果可以得到解决，也就是对于某个常数k，复杂度是n^k，其中n是输入的大小，比如每组的人数。拟多项式时间算法在时间n^(logn)k内执行，只比多项式时间差一点点，但起码比我们预计的NP完全问题所需要的2^n^ε的复杂性好的多。

Babai的证明结合了组合学和群论，是一个非常棒的工作。虽然距离让这个算法能够在多项式时间内执行完还有些远，但是Babai提供了一个重要的理论结果。这在P和NP完全问题之间取得了一项重大的进展。

电路设计

如果NP在完整的电路设计的基础上（也就是与或非门）没有最小的电路，那么就不存在P=NP的解。虽然在1980年代的电路发展黄金年代中，没有明确的证明否定P=NP的假设。在2009年的各项调查中，也说明在过去20年中，电路复杂性也没有取得重大的成果。在1987年，Razborov和Smolensky证明说不可能用与或非和Mod_p门的恒定深度电路计算某些固定素数p的多数函数。但是对于带有Mod_6门的电路来说，我们几乎无法证明这个结果。即便是我们可以证明NEXP（NP的指数时间版本）无法通过与或非和Mod_6门的小型、恒定深度的电路进行计算，P和NP是否相等的问题在几十年见也仍旧无法得到解答。话说回来，恒定深度的电路在理论上被认为是具有很弱的可计算性的，我们在这些年一直没有取得实质性的进展，在电路的算法最新产出上的无人问津也侧面证明了这个现象。

在2010年，Rayan Williams表明NEXP确实不具有那些使用Mod_6或其他Mod门一样的恒定深度的电路。因此，他创造了一种新的技术，使用可满足性算法进行解决。这种算法的实现下界比尝试所有可能，或者使用一些复杂性工具来暴力实现来说要好一些。后来，Williams和他的学生Cody Murray进行了进一步的研究，结果表明，可以在任何固定的没有带Mod_m门的小的恒定深度的电路中，都有非确定性拟多项式时间的解。然而，证明NP没有任意深度的小回路这个问题，仿佛仍然遥不可及。

复杂性的反击？

在2009年的那篇综述中，我在名为“新希望”的章节中讨论了一种新的几何复杂性理论方法，这个方法基于Ketan Mulmuley和Milind Sohoni开发的代数几何和表示论来攻克P和NP问题。简而言之，Mulmuley和Sohoni创建了高维的多边形空间，以在NP的代数版本中找到P和NP的映射，从而在这个空间中重构、理解并解决该问题。他们的一个猜想中，假设多边形包含某个表示理论对象的特殊属性。在2016年，Peter Burgisser、Christian Ikenmeyer和Greta Panova从理论上证明了这种方法是不可能滴。

虽然Burgisser和Ikenmeyer、Panova的研究成果否定了GCT分离P和NP的方法，但是并没有将这种实验方法和思路进行否定。人们仍然可以根据这种表示理论对象的数量创建不同的多边形空间。尽管如此，我们还是无法孤注一掷的认为多边形方法能够在不久的将来解决P和NP的问题。