一个听起来简单的问题产生的数字对我们的宇宙来说太大了广达杂志

由柏拉图重新发布

关注： 0

一个听起来简单的问题产生的数字对我们的宇宙来说太大了广达杂志柏拉图区块链数据智能。垂直搜索。人工智能。

5 岁的孩子能够掌握计算机科学前沿问题的情况并不常见，但这是有可能发生的。例如，假设一位名叫爱丽丝的幼儿园学生有两个苹果，但她更喜欢橙子。幸运的是，她的同学们开发了一个健康的水果交易系统，并严格执行汇率：比如说，放弃一个苹果，你就可以得到一根香蕉。爱丽丝能否通过捡起和卸下香蕉或哈密瓜来执行一系列交易，从而得到她最喜欢的水果？

听起来很简单。 “你可以去小学告诉孩子们，”说克里斯托夫·哈斯，牛津大学计算机科学家。 “人们会想，‘那一定很容易。’”

但爱丽丝困境背后的数学问题——称为向量加法系统的可达性问题——出人意料地微妙。虽然有些情况很容易解决，但计算机科学家们花了近半个世纪的时间才对这个问题有了全面的了解。现在，通过过去几年的一系列突破，他们已经确定了这个问题到底有多复杂。

事实证明，这个幼稚的问题极其荒谬，几乎是卡通化的复杂——如此复杂，以至于几乎所有其他问题都如此复杂。著名的困难计算问题看起来就像是儿戏。试着量化解决这个问题所需的努力，很快你就会面临如此大的数字，甚至计算它们的数字也会让你找到你从未听说过的数字。这些数字常常让人与宇宙的规模进行比较，但即使是这些类比也不够。 “这不公平，”说格奥尔格·蔡采是德国凯泽斯劳滕马克斯·普朗克软件系统研究所的计算机科学家。 “宇宙真是太小了。”

触手可及？

从本质上讲，可达性问题与称为向量的数学对象有关，向量是有序的数字列表。这些列表中的条目称为分量，向量中分量的数量称为其维数。例如，爱丽丝的水果库存可以用四维向量来描述（a, b, c, d), 其组成部分代表她在任何给定时间有多少个苹果、香蕉、哈密瓜和橙子。

矢量加法系统（VAS）是表示系统中状态之间可能的转换的矢量集合。对于爱丽丝来说，转移向量 (−1, −1, 1, 0) 代表用苹果和香蕉交换哈密瓜。 VAS 可达性问题询问是否存在任何允许的转换组合可以将您从特定的初始状态带到特定的目标状态，或者用数学术语来说，是否存在将起始向量转换为目标向量的转换向量之和。只有一个问题：描述系统状态的向量的任何分量都不能低于零。

“这对于现实模型来说是一个非常自然的限制，”说沃伊切赫·切尔温斯基，华沙大学计算机科学家。 “苹果的数量不能为负数。”

在某些系统中，很容易确定目标向量是否可达。但情况并非总是如此。计算机科学家对看起来简单的向量加法系统最感兴趣，在这些系统中，确定可达性有多困难并不明显。为了研究这些案例，研究人员首先定义一个数字来量化给定系统的大小。这个数字，表示为 n，包含维度数、转换数和其他因素。然后他们询问可达性问题的难度会以多快的速度增加 n 变大。

为了回答这个问题，研究人员使用了两种互补的方法。首先，他们搜索特别棘手的向量加法系统的示例，在这些系统中确定可达性需要一些最小程度的努力。这些最低水平被称为问题复杂性的“下限”——他们对研究人员说，“对于给定的系统来说，最棘手的系统 n 至少有这么难。”

其次，研究人员试图建立“上限”——即使在最恶劣的系统中，可达性的难度也受到限制。这些人说，“对于给定的情况，最棘手的情况是 n 最多就这么难。” 为了准确确定最棘手的系统中可达性的难度，研究人员尝试将下限向上推，将上限向下推，直到它们相遇。

噩梦的东西

矢量加法系统有着悠久的历史。自 1960 世纪 XNUMX 年代以来，计算机科学家就使用它们来建模程序，将计算分解为许多小块，并同时处理这些小块。这种“并发计算”现在已经无处不在，但研究人员仍然没有完全理解其数学基础。

1976年，计算机科学家理查德·利普顿朝着理解 VAS 可达性问题的复杂性迈出了第一步。他开发了一种构建系统的程序，其中确定一个状态是否可以从另一个状态到达的最快方法是绘制它们之间的一系列转换。这使他能够使用两个精心选择的状态之间的最短路径的长度来衡量可达性问题的难度。

利普顿当时证明他可以构建一个规模系统 n 其中两个状态之间的最短路径涉及超过 $latex 2^{2^n}$ 转换。这意味着确定系统可达性所需的工作量有相应的双指数下限。这是一个令人震惊的发现——双指数增长是计算机科学家的噩梦。事实上，即使是普通的指数增长，研究人员也常常犹豫不决，相比之下，指数增长就相形见绌了：$latex {2^5}= 32$，但 $latex 2^{2^5}$ 超过 4 亿。

大多数研究人员认为利普顿已经设计出了最复杂的矢量加法系统，这意味着他将下限提高到尽可能高的水平。在这种情况下，唯一缺少的是与之相匹配的上限——也就是说，证明不存在比确定可达性更困难的系统。但没有人知道如何证明这一点。计算机科学家恩斯特·迈尔（Ernst Mayr）最接近，当他证明 1981 年，原则上总是可以确定任何向量加法系统的可达性。但他的证明并没有对问题的难度给出任何定量的上限。有地板，但看不到天花板。

“我当然断断续续地考虑过这个问题，”利普顿说。 “但过了一段时间我就放弃了，据我所知，40 年来没有人取得任何进展。”

2015 年，计算机科学家热罗姆·勒鲁和西尔万·施密茨终于成立了定量上限 - 如此之高，以至于研究人员认为这只是第一步，可以降低以满足利普顿的下限。

但事实并非如此。 2019 年，研究人员发现了一个远高于 Lipton 的下限，颠覆了数十年的传统观点。 VAS 可达性问题比任何人预想的都要复杂得多。

权力之塔

2019年令人震惊的结果源于失败。 2018 年，Czerwiński 反驳了 Leroux 和菲利普·马佐维茨基现在在华沙大学担任计算机科学家，这将有助于在相关问题上取得进展。在随后的讨论中，研究人员偶然发现了一种构建超复杂向量加法系统的有前途的新方法，这可能意味着 VAS 可达性问题的新下限，而该问题的进展已经停滞了很长时间。

“在我看来，一切都与 VAS 可达性有关，”Czerwiński 回忆道。在一个教学负担较轻的学期，他决定与勒鲁、马佐维茨基和另外两名研究人员一起专注于这个问题—— 斯瓦沃米尔·拉索塔华沙大学和兰科·拉齐奇华威大学。

几个月后，他们的努力得到了回报。切尔文斯基和他的同事证明他们可以构建矢量加法系统，其中两个状态之间的最短路径通过称为四分法的数学运算与系统的大小相关，这使得噩梦般的双指数增长看起来很温和。

Tetration 是连接数学中最熟悉的运算的模式的直接扩展，从加法开始。加在一起 n 一个数字的副本，结果相当于将该数字乘以 n。如果相乘的话 n 数字的副本，相当于求幂，或者将数字提高到 n次幂。 Tetration（通常由一对向上的箭头表示）是此序列中的下一步： n 意味着对其求幂 n 产生力量之塔的时间 n 故事高。

很难理解 tetration 失控的速度有多快：$latex 2 uparrowuparrow 3$ 或 $latex 2^{2^2}$ 是 16，$latex 2 uparrowuparrow 4$ 刚刚超过 65,000，并且$latex 2 uparrowuparrow 5$ 是一个近 20,000 位数字。从物理上来说，写下 $latex 2 uparrowuparrow 6$ 的所有数字是不可能的——生活在如此小的宇宙中是一种负担。

在他们具有里程碑意义的结果中，Czerwiński 和他的同事证明了存在大小为 n 其中确定可达性的最佳方法是绘制一条涉及超过 $latex 2 uparrowuparrow n$ 转换的路径，这意味着一个新的下限，使 Lipton 的下限相形见绌。尽管四分法令人头晕目眩，但它仍然不是问题复杂性的最终定论。

至五金十亿及以上

就在 VAS 可达性复杂性令人震惊的新下限出现后几个月，Leroux 和 Schmitz 推下去他们三年前建立的上限，但他们并没有完全达到四分之二。相反，他们证明了可达性问题的复杂性不会比称为阿克曼函数的数学怪物增长得更快。

要理解该函数，请采用用于定义四分法的模式来得出其严峻的结论。序列中的下一个操作称为五次操作，表示重复四次操作；接下来是另一个用于重复五次操作的操作（六次操作），依此类推。

阿克曼函数，表示为 $latex A(n)$，是当您在数轴上的每一处停止操作的阶梯上移动一步时所得到的： $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$、$latex A(3) = 3^3$、$latex A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$，依此类推。 $latex A(4)$ 中的位数本身就是一个大约等于 1 quinquagintillion 的巨大数字 - 这是 1 后跟 153 个零的异想天开且很少需要的名称。 “别担心阿克曼五岁，”建议哈维尔·埃斯帕扎，慕尼黑工业大学计算机科学家。

Leroux 和 Schmitz 的结果在下限和上限之间留下了很大的差距——VAS 可达性问题的精确复杂性可能位于范围的任一端或之间的任何位置。切尔文斯基并不打算让这种差距继续存在。 “我们一直在努力解决这个问题，因为很明显这是我们一生中做过的最重要的事情，”他说。

最后的突破出现在 2021 年，当时 Czerwiński 正在为一名名叫 Łukasz Orlikowski 的二年级本科生提供咨询。他为 Orlikowski 分配了该问题的一个简单变体，以帮助他加快速度，Orlikowski 的工作帮助他们两人开发了一种新技术，该技术也适用于一般可达性问题。这让他们能够提高下限基本上——一直到勒鲁和施密茨的阿克曼上限。勒鲁独立工作，获得等效结果大约在同一时间。

最后，研究人员确定了可达性问题的真正复杂性。 Czerwiński、Orlikowski 和 Leroux 的下界表明，存在一系列逐渐变大的向量加法系统，其中两个状态之间的最短路径与阿克曼函数成比例增长。勒鲁和施密茨的上限表明，可达性问题不会变得比这更复杂——对于那些希望有一个万无一失的实际程序来解决它的人来说，这几乎没有什么安慰。这是一个引人注目的例子，说明看似简单的计算问题是多么微妙。