|
选自quantamagazine 机器之心编译 编辑：Panda 证明问题难以解决究竟有多难？元复杂性（meta-complexity）理论研究者数十年来一直探究这个问题。近期的一系列研究成果开始给出这个问题的答案。复杂性理论研究者正直面着最让人困惑的问题：复杂性理论本身。2007 年秋季学期的第一周，Marco Carmosino 拖着自己去上了一堂数学课，这是马萨诸塞大学阿默斯特分校计算机科学专业学生的必修课。Carmosino 是一位大二学生，他当时正在考虑退学去设计视频游戏游戏。上课的教授提出了一个简单的问题，而这个问题将改变他的人生轨迹：你怎么知道数学真的有用？「这让我坐正了身体开始用心听讲。」Carmosino 回忆说，他现在是 IBM 的一位理论计算机科学家。他报名参加了一个选修的讲库尔特・哥德尔（Kurt Gödel）的工作的讲座。哥德尔那让人头晕目眩的自我指涉论证第一次揭示了数学推理的局限性并为计算的基本局限性方面的所有未来研究工作奠定了基础。其中涉及了太多过于艰难的概念。「我完全无法理解，」Carmosino 说，「但我知道我希望能理解。」现如今，即使是经验丰富的研究者，在面对理论计算机科学领域核心的那个至今未被解决的问题时，也依然会感觉难以理解。这个问题就是著名的 P 与 NP 问题。从本质上讲，这个问题问的是：许多长久以来都被认为极其困难的计算问题是否实际上都可以轻松解决（通过一条我们尚未发现的秘密捷径），还是说是否就像大多数研究者猜测的那样，难题恒难？这个问题可以说就是可知事物的本质。尽管计算复杂性理论（研究的是不同问题的内在难度）领域的研究者们已经付出了数十年的艰辛努力，但 P 与 NP 问题的答案依然遥遥无期。我们甚至都不知道可能的证明应该从哪里开始。「这里没有路线图。」Michael Sipser 说，他是麻省理工学院（MIT）一位资深的复杂性理论研究专家，曾在 1980 年代耗费了数年时间与这个问题搏斗。「就好像是你进入了荒野之中。」看起来，证明计算问题难以解决本身就是一个难题。但为什么这个问题会这么难？而且这个问题究竟有多难？Carmosino 等研究元复杂性（meta-complexity）子领域的研究者研究的是将这样的问题重新表述为计算问题，通过将复杂性理论的透镜转向自身来推动这一领域向前发展。「你可能会想：哇，那挺酷的呀。也许这些复杂性理论研究者都疯了。」MIT 一位研究生 Rahul Ilango 说，他得到了该领域一些近期最为激动人心的成果。通过研究这些内向型问题，研究人员了解到：证明计算难度这一任务的难度与一些初看好像无关的基本问题密切相关。发现看似随机的数据中的隐藏模式有多难？如果确实存在真正困难的问题，那么问题困难的可能性有多大？「元复杂性接近事物的核心，这越来越明显了。」Scott Aaronson 说，他是德克萨斯州大学奥斯汀分校一位复杂性理论研究者。这是引领研究者从 P 与 NP 问题迈向元复杂性的漫长而曲折的故事。这并不是一段轻松的旅程 —— 道路上布满了错误的转弯和路障，而且它还一次又一次地循环回到自身。然而，对元复杂性研究者来说，进入未知疆域的旅程本身就是一种奖励。加拿大西蒙菲莎大学的复杂性理论研究者 Valentine Kabanets 说：从提出看似简单的问题开始，「你完全不知道会走向何方。」「P 与 NP 问题」这个听起来枯燥无味的名称来自复杂性理论研究者们的习惯 —— 他们习惯把计算问题分类成宽泛的「复杂性类（complexity class）」，然后给它们打上类似纳斯达克股票代码的标签。计算问题是指原则上可通过算法解决的问题，而算法则是指精确指定的指令列表。但是，并不是所有算法的用处都一样大，算法之间的差异暗示着不同类的问题之间的根本性差异。复杂性理论研究者面临的挑战是将这些暗示变成有关复杂性类之间的关系的严格定理。这些关系反映了关于计算的永恒不变的真理，其远远超越了任何具体的技术。Kabanets 说：「这就像是发现宇宙定律。」在数量不断变多的几百个复杂性类中，「P」和「NP」是其中最著名的两个。粗略地说，P 是一类很容易求解的问题，比如按字母顺序排列一个列表。NP 这一类则是有容易检验的解的问题，比如数独解密。由于所有容易求解的问题都容易检验，所以 P 中的问题也都属于 NP。但某些 NP 问题似乎难以解决 —— 你无法直接靠直觉就填满一个数独，而是需要先尝试许多可能性。有没有可能这种表面上的困难只是一种假象 —— 其实存在某种简单的技巧可以求解每个易于检验的问题？ 展示复杂性类 P 与 NP 之间的关系的维恩图。
如果是那样，那么 P = NP：这两个类等价。如果是这种情况，那么必然存在某种算法可以极大简化大规模数独求解、优化全球航线、破解最先进的加密技术以及自动证明数学定理等问题。如果 P ≠ NP，则许多原理上可以解决的计算问题实际上将永远无法解决。早在 P 与 NP 问题首次被提出之前很久，研究者们就已经在担忧形式化数学推理的局限性了 —— 事实上，这比现代计算机科学的诞生还要早得多。1921 年，那是在同一问题吸引了 Carmosino 的注意力的一个时间之前，数学家大卫・希尔伯特提出了一个研究计划，希望将数学建立在绝对确定性的基础上。他希望从一些简单的假设（公理）开始，推导出一套满足三大关键标准的统一的数学理论。希尔伯特的第一个条件是一致性（consistency），这是一项基本要求，即数学必须没有矛盾：如果可以基于同样的公理证明出两个相互矛盾的陈述，那么这整个理论都是无可救药的。但一个理论可以既没有矛盾，也存在局限。这就涉及到希尔伯特的第二个条件了：完备性（completeness）：其要求所有数学陈述要么可证明为真，要么可证明为假。他的第三个标准是可判定性（decidability），即要求有一个无歧义的机械流程来判定任何数学陈述是真还是假。在 1930 年的一次会议上，希尔伯特宣告说：「我们的口号应该是：『我们必定知道，我们必将知道。』」仅仅一年后，哥德尔就给希尔伯特的梦想带来了第一次打击。他证明「本陈述是不可证明的」这样的自我推翻（self-defeating）陈述可从任何适当的公理集推导出来。如果这样一个陈述确实是不可证明的，那么该理论就不是完备的；如果它是可证明的，那么该理论就是不一致的 —— 这个结果更糟糕。哥德尔还在同一篇论文中证明：任何数学理论都无法证明其自身的一致性。 大卫・希尔伯特、库尔特・哥德尔和阿兰・图灵身着正装的黑白照片。1920 年代，大卫・希尔伯特（左）希望让数学有更加坚实的基础。库尔特・哥德尔和阿兰・图灵后来证明希尔伯特的梦想无法实现。
研究者仍旧抱有希望：未来的某个数学理论可能不一定是完备的，但可能却能被证明是可判定的。也许他们可以开发出一些工作流程，能够在识别出所有可证明陈述的同时避开哥德尔提出的那样的让人恼火的命题。问题是没人知道如何推理得到这些假设存在的工作流程。然后在 1936 年，一位名叫阿兰・图灵的 23 岁研究生以当时人还不熟悉的计算领域的语言重新表述了希尔伯特的可判定性条件，并给了它致命一击。图灵构建了一个数学模型（被称为图灵机），它可以表示所有可能的算法；而图灵在论文《On Computable Numbers, with an Application to the Entscheidungsproblem》中证明如果希尔伯特方案确实存在，那么它就符合这个模型。然后他使用了类似哥德尔方法的自我指涉方法证明不可判定的陈述确实存在 —— 等价来说：任何算法都无法解决的不可计算问题。希尔伯特计划轰然坍塌：对于什么可以证明，什么可以计算，永远存在根本性的限制。但随着计算机从理论抽象变成真实的机器，研究者们认识到图灵对可解问题和不可解问题的简单区分留下了许多有待解答的问题。到 1960 年代，计算机科学家已经开发出了能快速求解一些问题的算法，尽管在其他人看来，已知的算法都慢得让人头痛。但要是问题的关键不是问题是否可解，而是求解它们的难度有多大呢？「一个丰富的理论出现了，而我们已经不知道答案了。」Carmosino 说。为了阐释难度问题是多么地令人困惑，让我们来看看两个涉及图（graph）的紧密相关的问题。图是由点（称为节点）和线（称为边）构成的网络。计算机科学家使用图来建模各种各样的东西，从量子计算到交通状况。 在含 12 个节点的图上的哈密顿路径。
哈密顿路径是指通过每个节点一次的路径。从原理上讲，这个问题明显是可解的：因为可能路径的数量是有限的，所以就算其它方法都不行，你也可以直接检验每一条路径。如果节点的数量很少，这没什么问题，但只要图的规模稍大一些，可能性的数量就会暴增到失控程度，让这种简单方法难以为继。有一些更复杂的哈密顿路径算法能更好地解决问题，但算法解决问题所需的时间总是会随图的大小呈指数增长。图不一定要非常大，最优秀的算法研究者可能就已经发现无法找到这样的路径了，至少是无法「在任意合理的时间内」。加利福尼亚大学圣迭戈分校复杂性理论研究者 Russell Impagliazzo 这样说，「我说的『合理的时间』是指『在宇宙毁灭之前』。」哈密顿路径问题还有一个有趣的性质。如果有人宣称找到了某个图的哈密顿路径，那么你可以快速检验这个解是否有效；即使这个图很大，检查起来也很容易。你只需要跟随该路径，一个接一个地勾选节点，然后检查并确保你不会两次勾选某个节点。如果最后你也没有错过任何节点，那么该路径便是哈密顿路径。 指数级算法和多项式算法的增长趋势。
运行这个检验解的算法所需的时间与图的大小成正比。这类算法属于一个更宽泛的算法类别：多项式算法；其运行时间的增长是图大小的多项式函数。相比于指数级增长，多项式增长的速度较为平缓，因此即使是很大的图，多项式算法也依然可行。Carmosino 说：「它的效率要高得多。」 在含 12 个节点的图上的欧拉路径。
哈密顿路径问题具有明显的不对称性：你可以使用一个快速的多项式算法检验一个解是否正确，但却需要指数级算法才能找到一个解。这种不对称性可能并不出人意料，毕竟欣赏一件艺术杰作比创作一件艺术杰作更容易，检验一个数学证明也比证明一个新定理更容易，然而并非所有计算问题都具有这样的不对称性质。事实上，就存在一个与寻找哈密顿路径问题非常相似但行为表现大相径庭的问题。同样假设你有一个图，但你要做的是找到一条「欧拉路径」，即穿过每条边刚好一次的路径。同样，在检验可能的解方面，存在多项式算法，但求解这个问题也存在一个多项式算法。这里就没有不对称性。在复杂性理论中，某些路径似乎比其它路径更容易找到。哈密顿路径问题和欧拉路径问题都属于复杂性类 NP，其定义包括所有可用多项式算法检验解的问题。欧拉路径问题也属于 P 类，因为可用一个多项式算法求解它，但目前来看哈密顿路径问题并非如此。为什么这两个图问题表面上如此相似，实际却又如此不同呢？这就是 P 与 NP 问题的本质所在。
一开始的时候，复杂性类看起来是很方便的分类方法，可以把相似但不直接相关的问题归类到一起 —— 之前没人想到寻找哈密顿路径与其它困难的计算问题有关。然后到了 1971 年，在被美国拒绝终身教职而转到多伦多大学后不到一年，复杂性理论研究者史蒂芬・库克（Stephen Cook）发表一项非凡的研究成果《The complexity of theorem-proving procedures》。他发现有一个特殊的 NP 问题有一个奇怪的特征：如果有一种多项式算法能解决这个问题，那么该算法也能解决 NP 类中的所有其它问题。库克的「普适」问题似乎是支撑看似困难的问题类别的一根孤柱，将它们与简单问题分开了。只需解决那一个问题，其它 NP 问题都会迎刃而解。 身着羊毛背心的史蒂芬・库克坐在一张桌子前。史蒂芬・库克与莱昂尼德・列文和理查德・卡普一起在 1970 年代形式地描述了 P 与 NP 问题。
库克怀疑世上根本就不存在针对他的普适问题的快速算法，他在那篇论文中间如此说到，并且还补充说：「我觉得投入相当大的努力去证明这个猜想是值得的。」事实证明，「相当大的努力」还是低估了。大约同一时期，苏联一位名为莱昂尼德・列文（Leonid Levin）的研究生在论文《Universal Sequential Search Problems》中证明得出了相似的结论，不过他还发现了几个不同的普适问题。此外，美国的复杂性理论研究者理查德・卡普（Richard Karp）通过论文《Reducibility among Combinatorial Problems》证明库克发现的普适性本身就几乎是普适的（其实列文发现的普适性也一样，只不过卡普和库克要多年之后才知道列文的研究成果）。几乎所有没有已知多项式算法的 NP 问题都有这样的性质，即几乎每个可以轻松检验的问题看起来都很难。这后来被称为 NP 完备性（NP-completeness）。这意味着哈密顿路径问题和数独等所有 NP 完备问题在某个精确的意义上都是等价的。「这些不同的自然任务有很多，而它们全都神奇地变成了同一个任务。」Ilango 说，「而我们仍然不知道是否可能解决这个任务。」确定任何 NP 完备问题的难度就足以解决 P 与 NP 问题。如果 P ≠ NP，则难易问题之间的界限就由数千个同样坚固的柱子支撑着。如果 P = NP，则这整座大厦就已经濒临崩塌，只等一块碎片落下。 用维恩图表示 P 与 NP 完备问题中的问题。
库克、列文和卡普将许多看似不相关的问题统一了起来。现在，所有复杂性理论研究者要做的就是解决这个问题：P = NP 是否成立？五十年后，这个问题依然没能得到解答。Kabanets 将对数学局限性的推理比作是探索一片全局状况未知的巨大疆域。一个拥有无限计算力的存在可以从最高的山顶俯瞰全局，一眼洞悉整个图景，但普通的凡人不能指望获得这种优势。他说：「我们这些山脚下的人也许可以试着上跳下窜，获得一个更好的视野。」假设 P = NP 成立。为了证明这一点，研究者需要找到一个用于 NP 完备问题的快速算法，这个算法可能隐藏在那个巨大图景中某个不起眼的角落。谁也不能保证他们能很快找到它：复杂性理论研究者在经过几十年的工作后偶尔会发现一些用于看似很难（尽管不是 NP 完备）的问题的精妙算法。现在假设 P ≠ NP。证明这一点还要更难。复杂性理论研究者必须证明不可能存在任何快速算法，这个任务的难度实在太大，实际上挫败了未来所有研究者。一大难点是研究者们根本不知道从哪里开始。但也不是说没有研究者尝试。过去几十年来，他们从不同角度向这个问题发起过冲击，但没一次都发现前进之路已被堵塞。「这是理论计算机科学领域最明显不过的事实之一。」Carmosino 说，「当面对一个如此持久的现象时，你肯定想获得一些解释。」在 Carmosino 上大学的最后一年，他的好奇心将他从哥德尔引向了复杂性理论的研究生课程。他惊讶地发现自己在作业上花费的时间多于在其激情项目上投入的时间 —— 这个项目是一个能学习童话故事的叙事结构并生成新故事的计算机程序。Carmosino 回忆说：「那时候我想：哇，我得认真对待这个问题。」没过多久，他就对这门学科产生了浓厚的兴趣，以至于他的导师都细心地建议他重新考虑毕业后的计划。「他说：你知道，如果你想继续做这个，如果你想继续研究理论计算机科学和复杂性理论，你可以继续：这叫做研究生学校。」Carmosino 说。获得硕士学位后，他于 2012 年来到圣地亚哥，在 Impagliazzo 的指导下攻读博士学位。 Marco Carmosino 身着蓝色衬衫和西装外套的照片。Marco Carmosino 在 1980 年代对一个重大成果的痴迷给他带来了灵感，让他在 20 年后为元复杂性领域带来了突破。
Carmosino 一开始的主要目标是更好地理解二十年前的一篇里程碑论文《Natural proofs》，它让他浮想联翩。这篇论文来自复杂性理论研究者 Alexander Razborov 和 Steven Rudich，其中证明：用于证明 P ≠ NP 的一种特定的「自然」策略几乎必定会失败，因为其成功的代价非常高（密码学的彻底崩溃），以至于研究者认为这非常不可能实现。研究者将 Razborov 和 Rudich 研究结果解释成无法使用这种常用方法来证明 P ≠ NP。对于复杂性理论领域的悬而未决的问题，有许多障碍，这个「自然证明障碍」只是其中之一。每一个障碍都像一块拦路石，警告着人们：这条看似有希望的路径其实是条死路。这些障碍合到一起，表明任何能解决 P 与 NP 问题的证明都必然截然不同于过去使用过的任何证明方法；也因此大多数研究者都相信 P 与 NP 问题的解依然遥遥无期。但至少这些障碍能告诉他们不用去某些地方找了。Ilango 说：「有如此之多的障碍，复杂性理论既是受诅咒的，也是被祝福的。」当 Carmosino 遇到这个自然证明障碍时，这个障碍已经存在了近 20 年时间。但他认为它带给研究者更多的是教训。他的这种感觉得到了证实。他与三位同事通过从元复杂性角度研究自然证明而证明了这个令人惊讶的结果。有几项重大成果引发了人们对元复杂性的新兴趣，他们的证明便是其中之一，并在过去几年中催生了一系列进展。但如果要了解从自然证明到元复杂性的研究轨迹，我们必须回到 1970 年代研究者们首次开始解决 P 与 NP 问题的时候。为什么证明问题很难的问题很难？一开始，研究者试图通过图灵用过的技术（图灵用来证明某些问题无法通过任何算法解决）的变体来证明 P ≠ NP，即证明某些 NP 问题无法通过任意可能的多项式算法解决。但他们很快在论文《Relativizations of the P=?NP Question》中发现了一个表明这些方法没有用的证明 —— 这是解决 P 与 NP 问题遇到的第一个主要障碍。所以他们开始寻找另一种方法，他们很快在图灵的同时代人克劳德・香农的研究成果中找到了一种。 克劳德・香农身穿西装的黑白照片。克劳德・香农在自己的硕士论文中发展出了一套基于电路的计算理论模型。
在密歇根州北部一个小镇长大的香农似乎不太可能成为信息时代的开创者。然而，他的成就体现了计算机科学这一新兴学科的跨学科性质 —— 电气工程和数理逻辑各半。香农在自己的硕士论文《A symbolic analysis of relay and switching circuits》中展示了可以如何使用机电开关组成的电路表示涉及布尔变量的逻辑表达式；布尔变量是指只能取两个值（比如真和假或 1 和 0）的量。在逻辑表达式中，布尔变量通过逻辑门与（AND）、或（OR）、非（NOT）连接到一起。举例来说，只有当 A 和 B 皆为真时，基本表达式 A AND B 才为真，否则为假；而只要 A 和 B 中至少一个为真，A OR B 便为真。NOT 门甚至更简单：它会翻转变量的真值。有了足够多这些基本的构建模块，就能执行任意计算。「当你看你的电脑时，究其根本，它到底在做什么呢？它在运行一个电路。」Ilango 说。香农的研究为理论研究者提供了一种思考计算问题难度的新方法，即「电路复杂性（circuit complexity）」，即便这里提到的电路只是数学抽象。有一段时间，研究者认为这种方法可以解决 P 与 NP 问题，但最终这条道路撞上了上述的自然证明障碍。 房屋大小的 Harvard Mark I（哈佛一型）计算机的黑白照片。这张照片摄于 1944 年，这台 Harvard Mark I 计算机的构建模块是机电开关，正如香农在其论文中分析的那样。
这个电路复杂性框架需要重新思考图灵的计算模型中最基础的概念。在这里，研究者考虑的不是计算问题和解决问题的算法，而是布尔函数和计算这些函数的电路。布尔函数以布尔变量（真或假，1 或 0）为输入，输出的也是真或假、1 或 0。与算法类似，电路描述的也是在任意输入下得到输出的过程。「我的理解是，人们开始研究电路复杂性，因为他们认为图灵机太复杂了。」MIT 复杂性理论研究者 Ryan Williams 说，「我们一个门接一个门地研究电路。」我们知道有许多用于解决特定计算问题的算法，其中一些算法比其它算法更快；类似地，也有许多不同的电路可以计算给定的布尔函数，其中一些电路的门数量比其它门更少。研究者将函数的电路复杂性定义成了计算该函数所需的最小电路的门总数。对于一个输入变量数量固定的函数而言，电路复杂度也是一个固定值 —— 某些函数的值高于其它函数。具有同样真值表的不同布尔电路。 但在很多情况下，可以通过增加输入变量的数量来获得同一函数的更复杂版本，就像我们可以用更大的图来让哈密顿路径问题更加困难。研究者在研究算法运行时间时也考虑了同样的问题：随着输入变量增多，用于计算一个布尔函数的门的最小数量的增长是呈多项式模式还是指数级模式？研究者将这两类函数分别称为「易于计算」和「难以计算」的函数。一种易于计算的布尔函数类似于 P 类中的计算问题 —— 可以通过在多项式时间内运行完成的算法解决的问题。但也有些函数类似于困难的 NP 问题，其中研究者使用已有的最好方法发现：计算更大的问题版本需要门的数量呈指数增长，然而其答案却可以被轻松验证。如果复杂性理论研究者可以证明世上不存在计算出这样一个函数的更好方法，那就能说明 P ≠ NP。这是 1980 年代大多数复杂性理论研究者所奉行的策略。他们的胜算很大。香农在 1949 年通过论文《The synthesis of two-terminal switching circuits》证明，几乎每一个布尔真值表（就是一个固定大小的布尔函数的所有可能输入和输出的长列表）的电路复杂度实际上都是尽可能高的。他使用了一个简单得让人惊讶的论据：组合少量门的方法比组合许多门的方法少得多。所以复杂性理论研究者发现自己陷入了一个奇怪的境地。如果几乎每个真值表都有很高的电路复杂性，那么几乎每个布尔函数都必然难以计算。研究者要做的就只有找到一个这样的函数，并确信其属于 NP 类。那会有多难？起初，进展迅速。1981 年，Sipser 与两位合作者写了一篇论文《Parity, circuits, and the polynomial-time hierarchy》，其中证明：如果一个特定的布尔函数使用的电路以一定的方式限制了门的排列方式，那么该布尔函数必定是难以计算的。Sipser 说：「我们想的是先用这些受限的模型来证明一些东西，然后在获得的成果上继续探究限制越来越少的情况。」Michael Sipser 身着蓝色纽扣衬衫。Michael Sipser 在 1981 年参与证明了一个基于受限电路的里程碑结果，但之后进展一直不佳。 1985 年，Razborov 迈出了下一大步。那时候他刚在莫斯科开始研究生生涯，而这项成果完全是意外所得，那时候他其实正在研究另一个数学分支的问题；结果表明解决 P 与 NP 问题是一个先决条件。「我就是太幸运了，我当时不知道这个问题有多难。」Razborov 说，「否则我可能甚至都不会开始。」在论文《Lower Bounds For The Monotone Complexity Of Some Boolean Functions》中，Razborov 分析了仅包含与门和或门的电路，并证明：无论如何排布这些门，使用这样的电路都难以计算一个特定的函数 —— 更重要的是，已知该函数就是 NP 完备的。为了解决 P 与 NP 问题，研究者要做的就只是将 Razborov 的技术扩展用于有非门的电路。Razborov 说：「那时人们普遍有种感觉：只要再进一步，再获得一次发现，我们就能成功。」但那没有发生。Razborov 自己证明他的方法无法证明带有非门的情况，也没人能找到其它前进之路。多年以后，他开始思考这条路无法继续的原因。Rudich 在美国思考着同样的问题。他和 Impagliazzo 是大学同学，后来一起读研究生。他们的友情起点是他们都深深着迷于哥德尔和图灵的自我指涉证明以及他们对数学和计算机科学基础所造成的影响。Impagliazzo 说：「我们开玩笑说，我们会得到一个写着『自我指涉』的按钮」。身穿蓝色毛衣的 Alexander Razborov 和身穿蓝色衬衫的 Steven Rudich。Alexander Razborov（左）和 Steven Rudich 在 1994 年发现了自然证明的障碍，这能解释为什么之前对 P ≠ NP 的证明尝试都失败了。 在读研究生时，Rudich 和 Impagliazzo 都研究过密码学的复杂性理论基础 —— 密码学也许能提供尝试证明 P ≠ NP 的最佳实践动机。加密学家隐藏秘密消息的方法是用「伪随机性」来隐藏它们 —— 以这种方式加密的消息在任何窃听者看来都像是随机排布的数字，但却可以被目标接收者解码。但我们能以何种方式确保潜在的窃听者会觉得破解太难而选择放弃呢？这就是复杂性理论的用武之地。当今使用最广泛的加密方法都基于看似困难的 NP 问题 —— 要解密信息，攻击者需要一种尚未发现的快速算法来求解这个问题。为了确保这些方法是真正安全的，就需要证明 P ≠ NP。Sipser 说，如果没有对此的证明，你就只能「希望试图窥探你秘密之人不是比你优秀的数学家。」尽管密码学本身确实也让人着迷，但似乎与最早将 Rudich 和 Impagliazzo 引入该领域的自我指涉论证相距甚远。但正当 Rudich 努力理解电路复杂性方法止步不前的原因时，他开始意识到这两个学科的距离其实并不远。研究者为证明 P ≠ NP 所采用的策略具有一种自我推翻（self-defeating）的特性，这让人想起了哥德尔的著名命题：「本陈述是不可证明的」—— 而密码学可以帮助解释其原因。大概在同样时间，Razborov 在俄罗斯发现了类似的联系。这些都是自然证明障碍的种子。自然证明障碍的核心关键是：区分高复杂度函数和低复杂度函数的任务类似于区分用于加密信息的真随机性和伪随机性的任务。我们希望证明高复杂度函数与低复杂度函数有本质区别，从而以此证明 P ≠ NP。但我们也希望无法区分伪随机性与真随机性，从而依然对密码学的安全性充满信心。也许我们无法两者兼得。1994 年，Razborov 和 Rudich 意识到他们有相似的见解，于是开始合作，将他们的研究成果结合起来。他们首先观察到，之前所有利用电路复杂性证明 P≠NP 的尝试都采用了同样的一般性策略：确定一个 NP 完备的布尔函数的特殊属性，然后证明易于计算的函数都不可能具有该属性。这能证明所选的 NP - 完备函数确实难以计算，从而证明 P ≠ NP。Sipser 和 Razborov 等研究者都成功使用这一策略证明出了更有限的结果；在每一种情况下，研究人员认定的特殊性质是大多数布尔函数都具有的性质。由于之前还没有描述这种属性被广泛具备的情况的术语，Razborov 和 Rudich 创造了 natural proof（自然证明）这一术语。如果「不自然」证明可能存在，那么它们必定非常反自觉，所以也担得起这个名字。Razborov 和 Rudich 后来证明了他们的主要结果：对 P ≠ NP 的自然证明需要非常全面地理解易于计算的函数和难于计算的函数的差异之处；而这样的知识也可助力找寻用于识别易于计算的函数的快速算法，即便这些易于计算的函数表面上看可能很难。如果复杂性理论研究者成功使用自然证明证明了 P ≠ NP，他们就能发现一种近乎万无一失的方法 —— 只需看一眼任意真值表，就能确定对应函数的电路复杂性是高是低。这是比他们想要证明的结果更强大更普适的结果。Carmosino：「你无法控制，你会得到比自己想要的更多。」这就好比你想检验某个特定陈述的事实，但每次尝试都会得到一个通用测谎仪的设计蓝图 —— 这也太好了吧，简直不像是真的。对于复杂性理论研究者来说，自然证明力量惊人，但这也让其成功的可能性变得很小。但如果有这样一个证明成功了，那么由于电路复杂性和伪随机性之间的关联，这个意料之外的结果对密码学来说就是个坏消息了。要理解这种关联，可以这样想象：在有许多输入变量的布尔函数的真值表的输出列中，使用 1 替换每一个「真」，使用 0 替换每一个「假」。可用 0 和 1 表示布尔真值表的输出 如果这个布尔函数的电路复杂性很高，那么这个很长的输出列表原则上就无法与真正随机的 0 和 1 构成的字符串区分开 —— 比如通过不断掷硬币得到的字符串。但如果该函数的电路复杂性较低，这个字符串必定有一个简单的简明描述，即便其可能看起来很复杂。这使其非常类似密码学使用的伪随机字符串，其简明描述便是那表面的随机性之下隐藏的秘密消息。伪随机字符串可能看似随机，但实际有一个简单的描述。 所以 Razborov 和 Rudich 的研究结果表明：对 P ≠ NP 的任何自然证明都会得到一个快速算法，该算法能将包含隐藏信息的伪随机字符串与真随机字符串区分开。安全的加密将因此而不再可能 —— 这与研究者试图通过证明 P ≠ NP 取得的目标刚好相反。另一方面，如果安全的加密可能实现，那么自然证明就不是一种证明 P ≠ NP 的可行策略 ——P ≠ NP 是安全加密的先决条件。简而言之这就是自然证明障碍。看起来，复杂性理论研究者正在接收一个残酷的玩笑。Kabanets 说：「如果你相信难度，那么你就应该相信难度是很难证明的。」P≠NP 猜想的含义与证明该猜想的难度之间存在有趣的联系，但要确定这种联系却很难。一方面，自然证明障碍只是阻碍一条证明 P ≠ NP 的途径。另一方面，它没有将证明 P ≠ NP 的难度与 P ≠ NP 自身关联起来，而是关联了安全加密方法的存在 —— 这是一个紧密相关但并不完全等价的问题。为了真正理解这种关联，研究者必须熟悉元复杂性。「人们有一种直觉：因为 P ≠ NP，所以难以证明 P ≠ NP。」Williams 说，「但为了理解这种直觉，你必须开始思考把证明 P ≠ NP 这样的任务作为计算问题。」Valentine Kabanets 戴帽子的户外照。Valentine Kabanets 在读研究生时写了一篇颇具影响力的论文，其中论述了一个典型的元复杂性问题，他将其命名为「最小电路规模问题（MCSP）」。 「我当时想做一些学术性更强的事情。」Kabanets 回忆说，「我也很想看看这个世界。」他来到加拿大读研究生，正是在这里他了解到了自然证明障碍。Kabanets 和 Carmosino 一样被这一结果迷住了。他说：「这一联系看起来意义重大。」2000 年，在他的研究生阶段行将结束时，他发现自然证明障碍经常出现在他与 Jin-Yi Cai（蔡进一）的对话中，蔡进一是一位复杂性理论研究者，当时正在多伦多学术休假。他们不再将这个障碍看作是一块拦路石，而是一份邀请 —— 一个探究「证明问题很难」这个任务到底有多难的机会。他们给出这一新视角的论文《Circuit minimization problem》将成为新生的元复杂性领域最富影响力的早期研究成果之一。Kabanets 和蔡进一的论文强调了 Razborov 和 Rudich 形式化描述的自然证明障碍中隐含的一个计算问题：给定一个布尔函数的真值表，确定其电路复杂性是高还是低。他们称之为最小电路规模问题（MCSP）。MCSP 是一个典型的元复杂性问题：这类计算问题关注的不是图论或其它外部主题，而是复杂性理论本身。实际上，它就像是 1980 年代那个问题的定量版本 —— 这个问题促使复杂性理论研究者使用电路复杂性方法来解决 P 与 NP 问题；这个问题就是：哪些布尔函数难以计算，哪些又易于计算？「如果我们能想出一种 MCSP 算法，那就会成为一种自动化复杂性理论研究的方法。」Impagliazzo 说，「它至少能让我们深入了解可以如何更好地完成我们的工作。」复杂性理论研究者并不担心这种神奇的算法会让他们失业 —— 他们认为它根本就不存在，因为 Razborov 和 Rudich 的研究表明这种用于分辨高与低复杂度真值表的算法会让安全加密变得不可能实现。这意味着 MCSP 很可能是一个困难的计算问题。但这个问题究竟有多难？它是 NP - 完备的吗，就像哈密顿路径问题等研究者们在 1960 年代苦苦探究的问题？对于 NP 问题而言，「有多难？」通常容易回答，但 MCSP 似乎是一个奇怪的例外。Kabanets 说：「我们有一些很少的『漂浮不定的』问题，它们没有连接到 NP 完备问题之岛，即便它们看起来很难。」Kabanets 知道他和蔡进一并非最早思考被他们命名为 MCSP 的问题。苏联的数学家早在 1950 年代就研究过一个非常相似的问题，那时候他们是想尝试理解不同计算问题的固有难度。莱昂尼德・列文在 1960 年代末发展后来的 NP - 完备性理论时也曾与这个问题搏斗过，但他没能证明它是 NP 完备的，而且他发表的开创性论文中也没有它。之后 30 年里，这个问题都鲜有人关注，直到 Kabanets 和蔡进一注意到了其与自然证明障碍之间的联系。Kabanets 当时并不指望靠自己解决这个问题 —— 他想做的是探索其如此之难的原因以证明：这个看似困难的关于计算难度的问题实际上很难。牛津大学复杂性理论研究者 Rahul Santhanam 说：「从某种意义上说，这是元 - 元复杂性（meta-meta-complexity）」。但是，是这个问题一直都很难，还是说至少存在某种方法可以解释为什么研究者没能成功证明 MCSP 是 NP 完备的？Kabanets 发现确实存在一个原因：理解电路复杂性的困难就像是一个障碍，阻碍着研究者使用任何已知的策略来证明 MCSP 的 NP 完备性，而 MCSP 这个问题本身就是关于理解电路复杂性的困难的。自然证明障碍那扭曲的、自我推翻的逻辑似乎无法避免。MCSP 也有可能不是 NP 完备的，但这也似乎不太可能 —— 人们已经知道该问题某些更简单的变体是 NP 完备的。此维恩图展示了 MCSP 在 NP 类计算问题中的位置。 Impagliazzo 说：「我们不知道该把这个问题置于何处，使之能与我们研究的其它问题直接联系起来。」Kabanets 已经阐明了 MCSP 的奇怪行为，但他不知道如何才能更进一步。元复杂性研究速度放缓了。16 年后，研究者发现其与另一个基础问题之间存在惊人的联系，这时候元复杂性研究才再次迎来繁荣。这个基础问题是：如果我们只关心得到大多数时候都正确的答案，那么解决问题有多难？对于日常问题来说，大多数情况下有效的答案往往就已经足够好了。举个例子，规划交通时，我们往往是根据典型的交通模式，而非最糟糕的情况。大多数复杂性理论研究者都难以满足：如果他们能找到一种能为每个可能输入得到正确答案的快速算法，他们才会满足地宣布这个问题是容易的。这种标准方法是根据研究者所称的「最坏情况」复杂度来对问题进行分类的。但还存在一种「一般情况」复杂性理论，即如果存在一种能在大多数输入下都能得到正确答案的快速算法，则该问题就可被视为是容易的。这种区别对密码学研究者来说很重要。请想象有这样一个计算问题，其几乎所有输入都容易求解，只有少数情况例外 —— 即使最好的算法也无能为力。最坏情况复杂性理论把这视为一个困难问题，但对密码学而言这没有任何用处。如果你的消息中仅有一部分难以解码，哪还有什么意义呢？最早开始严格地研究一般情况复杂性理论的正是列文，那是在他完成了自己在 NP 完备性方面的开创性成果的十年之后。列文在 1978 年移民到了美国，到 1980 年代中叶，他的注意力转向了一般情况复杂性。他开始与其他人合作进一步推进这一理论，其中包括当时正在读研究生的 Impagliazzo。但在他们取得进展的同时，Impagliazzo 发现研究者们常常自说自话。他希望每个人都达成一些共识，而列文的论文又是出了名地简洁 —— 开创一般情况复杂性领域的论文《Average Case Complete Problems》不到两页长。Impagliazzo 说：「我打算把莱昂尼德的研究成果翻译成更通俗易懂的专业术语。」他决定先写一些简短的带着打趣玩笑的综述，在深入数学内容前描绘一番该领域的概况。「这部分内容变成了整篇论文的代表，也是大家唯一记得的部分。」这篇论文是《A personal view of average-case complexity》，在 1995 年一发表出来便成了经典。针对按照不同计算难度和不同加密能力划分的五个世界，Impagliazzo 为它们起了些古怪离奇的名字。我们生活在其中一个世界，但我们不知道是哪一个。身穿红色毛衣的 Russell Impagliazzo 与身穿黄色衬衫坐在室外的莱昂尼德・列文。莱昂尼德・列文（右）于 1980 年代中期开始研究一般情况复杂性。Russell Impagliazzo 之后写了一篇关于我们生活的五个计算世界的标志性论文，让这一学科更为人所知。 自 Impagliazzo 的论文问世以来，研究者就一直梦想着消除其中的微型多元宇宙部分 —— 通过证明某些世界根本不可能存在来缩小可能性范围。有两个世界是尤其诱人的目标：在这两个世界中，即便 P ≠ NP，加密也是不可能的。其中一个世界被称为 Heuristica（启发之地）；在这个世界中，所有 NP - 完备的问题都在大多数输入上容易求解，但快速算法偶尔会出错，所以在最坏情况复杂性理论的标准下，这些问题会被认为是困难的。这是一个加密不可能实现的世界，因为几乎每个代码都容易被破解。另一个世界则名为 Pessiland；这也是一个加密不可能实现的世界，但原因不同：每个问题在一般情况复杂性标准下都是困难的，但对信息加密之后，即便是预期的接收者也将无法辨别。事实证明，这两个世界与元复杂性问题紧密相关 —— 尤其是 Heuristica，其关乎着 MCSP 是否 NP 完备这个长时间都未能得到解决的问题。这个让 Kabanets 着迷并阻碍列文如此之久的问题不仅仅是一个满足好奇心的问题：它还关乎一整个世界。为了排除 Heuristica 的可能性，研究者必须弥合最坏情况和一般情况复杂性之间的区别 —— 也就是说，他们必须证明：假设存在能在大多数输入上正确解决一个 NP 完备问题的算法，那么该算法实际上能在所有情况下解决该问题。这种关联被称为「最坏情况到一般情况的约简」。人们已经知道某些特定问题存在这种现象，但它们都不是 NP 完备的，因此这些结果无法说明更一般的情况。在基于 P ≠ NP 这一单一假设实现安全加密的梦想之路上，如果能消除 Heuristica，密码学家就算取得了一半的成功。2003 年，两位复杂性理论研究者在论文《On worst-case to average-case reductions for NP problems》中表明：用于为已知 NP 完备问题证明最坏情况到一般情况的约简的现有方法都会有极不寻常的后果，这表明这样的证明也许不可能存在。研究者们就不得不去找寻另一种方法，而现在他们认为 MCSP 也许正是他们所需的问题。但他们要到十多年后才明白这一点。Marco Carmosino 对自然证明障碍的执着和痴迷让他最先看到了这两者之间的联系。Carmosino 最早与元复杂性研究相遇是在其研究生阶段，那时候他读到了 Kabanets 与另外四位研究者在 2013 年发表的一篇论文《Mining Circuit Lower Bound Proofs for Meta-Algorithms》，其中进一步发展了 Kabanets 在十多年前开创的用于自然证明障碍的方法。这让他更加坚信，还能从 Razborov 和 Rudich 的经典论文中学到更多东西。「那时候我对那篇论文着迷了。」Carmosino 说，「到现在一切都没变。」这种痴迷最终带来了收获；那是在加州大学伯克利分校的一个为期一个学期的研习班上，他来到这里并把大部分时间都用于与 Impagliazzo、Kabanets 和 Antonina Kolokolova 讨论。Antonina Kolokolova 是来自纽芬兰纪念大学的一位复杂性理论研究者，她是 Kabanets 2013 年那篇论文的合作者之一。Carmosino 曾与他们三人合作过一次，那次成功合作给了他信心，让他不断向他们提出有关这一主题的最让自己着迷的问题。Kabanets 回忆说：「他在骚扰人，但方式是好的。」一开始的时候，Carmosino 有一些新想法，可用于证明出现在 Razborov 和 Rudich 的关于自然证明障碍的论文中的那个版本的 MCSP 的 NP 完备性。但这些想法没能取得成功。相反，Impagliazzo 的一句随口之言让那四位研究者意识到，自然证明障碍可以衍生出比任何人以为的都更强大的算法 —— 这个路障之上篆刻着一副隐秘地图。Antonina Kolokolova 身穿一件蓝色毛衣坐在一张桌子前。2016 年，Antonina Kolokolova 与 Carmosino、Impagliazzo 和 Kabanets 共同证明 MCSP 与学习之间存在惊人的联系，这让人们再次关注起元复杂性。 在 2016 年的论文《Learning algorithms from natural proofs》中，这四位研究者证明：一种特定类别的一般情况 MCSP 算法可用于构建一种最坏情况算法 —— 该算法可用于识别看似随机的数字串中隐藏的模式。该任务被计算机科学家称为「学习（learning）」。这个结果很惊人，因为直觉上看，学习似乎比 MCSP 算法执行的二元分类任务更难 —— 高复杂度或低复杂度。而且出人意料的是，它将一个任务的最坏情况复杂性与另一个任务的一般情况复杂性联系到了一起。Impagliazzo 说：「这种联系的存在并不是显而易见的。」对于一般布尔电路来说，MCSP 的快速算法仅仅存在于假设中：除非能证明 MCSP 是一个容易的计算问题，否则这个快速算法不可能存在，尽管所有的证据都指向相反的结论，这意味着这四位研究者的论文所暗示的学习算法同样仅存在于假设之中。但对于 MCSP 的一些更简单的版本 —— 在对电路有特定限制时，区分高复杂度真值表和低复杂度真值表 —— 快速算法早已为人所知多年。Carmosino、Impagliazzo、Kabanets 和 Kolokolova 的论文表明，这些算法可以转换为学习算法，这些算法同样受到限制，但仍然比研究者以前在如此严格的理论层面上理解的任何算法都要强大。Ilango 说：「不知为何，它们的自我指涉方面让你能做一些似乎无法对更标准的问题做的事情。」这一结果吸引了研究其它课题的复杂性理论研究者的关注。对于将在未来几年发现的元复杂性和一般情况复杂性之间的进一步联系，这一结果也算是一个预演。最重要的是，这一结果证明：研究者可以通过提出简单问题来解决那些初看似乎只会阻碍他们前进的障碍。「这种两面性是过去至少三四十年复杂性研究的一大主题。」Impagliazzo 说，「障碍往往也是机遇。」Carmosino 及同事们发表了那篇论文之后几年，研究进展加快了。复杂性研究百年史 「新成果正在出现。」Kolokolova 说，「现在有很多非常非常聪明的年轻研究者。」Ilango 就是这样一位年轻研究者 —— 在读研究生的前三年，他攻克了证明 MCSP NP 完备性这一悬而未决的艰巨难题，他使用了一种双管齐下策略：一方面是证明 MCSP 的更简单版本的 NP 完备性，正如电路复杂性研究者在 1980 年代攻坚 P 与 NP 问题那样，见论文《The Minimum Formula Size Problem is (ETH) Hard》；另一方面是证明更复杂版本的 NP 完备性，这些问题直觉上看来更难，因此更容易证明它们很难，见论文《Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0 [p]》。Ilango 将自己对元复杂性的研究兴趣归功于 Eric Allender，他是罗格斯大学一位复杂性理论研究者，也是少数几位在 2000 年代和 2010 年代早期仍继续研究元复杂性的研究者之一。Ilango 说：「他的热情很有感染力。」另一位受到 Allender 激励的年轻研究者是平原秀一（Shuichi Hirahara），他现在是东京国立情报学研究所的一位教授。2018 年平原还是一位研究生时，他就揭示出了 Carmosino 与其合作者发现的元复杂性和一般情况复杂性之间的关系的真实程度。那四位研究者已经发现一个问题（MCSP）的一般情况复杂性与另一个问题（布尔学习）的最坏情况复杂性之间存在联系。平原进一步发展了他们的技术，在论文《Non-Black-Box Worst-Case to Average-Case Reductions within NP》中推导了 MCSP 从最坏情况到一般情况的约简。他的研究结果表明一种假设存在的一般情况 MCSP 算法（就像 Carmosino 及其同事考虑过的那个）实际上是足够强大的 —— 足以毫无差错地求解一种稍有不同的 MCSP。平原的研究结果激动人心，因为很多研究者猜测 MCSP 是 NP 完备的，这不同于其它所有已经知道从最坏情况到一般情况约简的问题。如果他们能扩展平原的结果，使之覆盖所有一般情况算法，然后证明 MCSP 是 NP 完备的，那就能证明我们的世界不是 Heuristica。Santhanam 说：「那会是一个震天撼地的结果。」证明 MCSP 是 NP 完备的似乎是一项艰巨的任务 —— 毕竟，这个问题已经悬而未决了 50 多年。但在平原 2020 年的突破性研究成果《NP-Hardness of Learning Programs and Partial MCSP》之后，研究者们现在离证明它要近得多了，超出了几年前任何人的预期。平原证明了该问题的一个名为部分 MCSP（partial MCSP）的变体版本的 NP 完备性；在部分 MCSP 中，每个真值表中都有一部分条目被忽略。他的证明基于 Ilango 开发的方法，其表明部分 MCSP 等价于一个看似无关的问题，该问题涉及一种名为秘密共享（secret sharing）的加密技术。这种方法是把已加密的消息分给许多人，使得只有当一定比例的人合作起来才能将其解码。对密码学的任何真实应用而言，你都希望提前知道这个比例是多少，但借助于额外的密码学技巧，你可以构建一个令人沮丧的场景，其中光是知道需要多少人合作就已经非常困难。平原找到了一种方法来证明这个假定的密码学问题是 NP - 完备的，然后他又证明这个证明也意味着部分 MCSP 的 NP 完备性。身穿蓝色衬衫的 Rahul Ilango 与身穿蓝色西装外套的平原秀一。Rahul Ilango（左）与平原秀一最近开发一种新的加密技术来证明 MCSP 的一种变体是 NP 完备的。 这一结果给元复杂性研究者带来的激励甚至超过平原更早的研究成果，其他研究者也注意到了它 —— 复杂性理论研究者和博客作者 Lance Fortnow 将其称为当年的年度成果。这是因为解决计算问题的这种「部分函数」版本一直都是其它 NP 完备性证明的一个关键中间步骤。「这是一项了不起的成果。」Williams 说，「所有人都曾以为这些部分问题的难度与完整问题大致一样。」此维恩图展示了分类 MCSP 变体版本的复杂度的最近进展。 在证明完整版的 MCSP 的 NP 完备性方面，障碍依然存在。但这些障碍表现出的样子说明解决它们并不需要一套全新的工具 —— 关键可能就只是找到一种正确组合已知技术的方式。如果能成功证明，就能分类一个自复杂性理论诞生以来就一直未被成功分类的问题，而这样一直未被分类的问题可不多。列文在一份电子邮件中写道：「这会让我感到谦卑，因为这说明我很愚蠢，竟没能看到它。」MCSP 甚至不是唯一一个实现了重大突破的元复杂性问题。2020 年时，在论文《On One-way Functions and Kolmogorov Complexity》中，康奈尔大学科技校区的密码学家 Rafael Pass 与其研究生刘研绎（Yanyi Liu）发现一个不同的元复杂性问题与一种基础加密协议之间存在某种联系 —— 这个加密协议定义了 Heuristica 和 Pessiland 的疆界，而 Pessiland 是 Impagliazzo 定义的世界中最糟糕的那个。（在 Pessiland 中，NP 完备问题在一般情况下是困难的，但加密也不可能实现。）这使得他们研究的问题成为了攻击 Pessiland 的主要候选问题，而他们更近期的一项研究成果《On one-way functions from NP-complete problems》表明这也能用于证否 Heuristica。「这幅拼图缺失了不同的碎片。」Pass 说，「在我看来，这些领域的联系是如此紧密，实在太神奇了。」平原警告说，对于想要证否 Impagliazzo 在 30 年前创造的某些世界的研究者而言，挑战依然存在。他说：「我想说的是，Heuristica 和 Pessiland 将会在某个时刻被排除掉，但我不知道我们离那一刻还有多远。」很多研究者预计最大的困难将是弥合两种不同的一般情况复杂性模型之间看似无关紧要的差距。密码学研究者通常研究的是在两个方向上都会出错的一般情况算法 —— 偶尔会将随机字符串错误地标记成伪随机或把伪随机字符串错误标记成真随机。而平原从最坏情况到一般情况的约简则适用于仅会犯第一类错误的一般情况算法。类似这样的微妙差异在复杂性理论领域却是天差地别。尽管有这个以及其它许多阻碍，但 Allender 还是不禁发出了谨慎乐观的声音。「我尽量让自己不要过于乐观，因为过去的研究历史表明没什么是行得通的。」他说，「但我们正在见证很多真正激动人心的发展 —— 克服那些似乎是障碍的方法。」在解答 P 与 NP 问题（或者仅仅是为了理解它）的过程中，如果说研究者从自己的苦苦求索中获得了什么教训，那就是复杂性理论本身就很复杂。但这种挑战性正是这条求索之路的意义所在。「这个问题如此之难实际上算是件好事。」Carmosino 说，「我永远不会感到无聊。」原文链接：https://www./complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/
|
