计算机科学家证明某些问题从根本上很难

计算机科学家 Nutan Limaye、Srikanth Srinivasan 和 Sébastien Tavenas（从上到下）设计了一种方法来证明某些算术问题确实很难。

（从上到下）由 Nutan Limaye 提供；塞巴斯蒂安·克罗格·克努森；奥伯沃尔法赫数学研究所的图片档案

令人惊讶的是，这些发现不需要新的框架或工具。相反，作者想出了如何绕过由 Wigderson 与耶路撒冷希伯来大学的 Noam Nisan 合作数十年的工作中出现的数学障碍。

丹麦奥胡斯大学的Srikanth Srinivasan与哥本哈根 IT 大学的Nutan Limaye 和尚贝里萨沃伊勃朗峰大学的Sébastien Tavenas共同撰写了这项新工作，他说：“我们意识到有一种非常愚蠢的方法可以绕过它。”法国。 “而且感觉如果有一种简单的方法可以做我们认为不可能的事情，那么肯定应该有更进一步的方法。”

重要问题

在 1960 年代，在计算机出现了几十年之后，出现了一种令人不安的趋势。科学家们已经成功地创建了算法来让他们的计算机解决各种问题，但有时这些算法花费的时间太长——比实际时间更长。

他们开始怀疑有些问题只是根本上很难，无论问题的规模如何。例如，考虑一组带有连接它们的边的点，称为图。一个重要的问题是确定是否存在一条称为哈密顿路径的路径，它沿着边缘行进，只访问每个点一次。按理说，如果增加点（和边）的数量，则需要更长的时间来确定是否存在这样的路径。但是最好的算法随着规模的增加而花费的时间呈指数增长，这使得它们变得不切实际。

许多其他问题似乎也需要指数级的时间。计算机科学家将继续证明，任何能够以某种方式有效地解决其中一个难题的算法都可以转换为对其他类似困难的算法做同样的事情。他们称这类问题为 NP。当 Wigderson 提到“我们希望解决的所有问题”时，他指的是 NP 中的问题，这些问题在许多情况下都会出现。

当然，也有很多看起来不难的问题，也没有花多少时间来解决。计算机科学家表明，这些问题中的许多在某种意义上也是等价的，他们称这一类为 P。他们怀疑 NP 问题确实比 P 问题更难，并且 NP 中的问题永远无法有效解决。但如果没有证据，他们总是有可能是错误的。

计算机科学家开始寻找方法来证明 NP 问题确实更难，研究人员正式将这个问题称为 P 与 NP。要回答这个问题，只要证明一个难题确实需要指数级的时间就足够了，但他们不知道该怎么做。因此，他们寻找其他可能不那么难确定硬度的途径。

到底有多难？

一组特定的问题似乎恰到好处。这是只依赖于加法和乘法的集合。例如，给定一组点，可以仅通过添加和乘以关于点的数据来计算所有可能的哈密顿路径（如果存在的话）。 （如果允许其他操作，例如比较值，也可以进行相同的计数，但问题和解决方案会变得更加复杂。）

此外，这组更简单的“算术”问题反映了更复杂任务的更大范围。也就是说，随着问题规模的增加，一些算术问题（如计算哈密顿路径）似乎需要更多的时间。 1979 年，哈佛大学的 Leslie Valiant 证明了许多算术问题在难度上是等价的，而其他问题在难易度上是等价的。计算机科学家后来以他的名字命名这些类别——分别是 VNP 和 VP。

与 P 与 NP 问题一样，无法证明 VNP 问题的难度。计算机科学家以一种新的形式重新发现了 P 与 NP 问题——VP 与 VNP——只是现在他们有了一个关键优势。 VNP 问题比 NP 问题更难，因为它们建立在它们之上：计算路径需要您能够确定路径是否存在。如果你想证明某件事是困难的，你就需要尽可能多的困难。

“它比 NP 更难，”Shpilka 说。 “因此证明这很困难应该更容易。”

在随后的几十年中，计算机科学家在 VP 与 VNP 问题上取得的进展比他们在 P 与 NP 问题上取得的进展要大得多，但其中大部分仅限于 Valiant 创建的称为代数复杂性的子领域。直到 Limaye、Srinivasan 和 Tavenas 最近的工作，他们仍然很难判断是否存在任何一般意义上的算术问题。

调整多项式

要了解这项新工作，有助于了解计算机科学家如何思考加法和乘法问题。从数学上讲，这些问题完全可以被称为多项式的表达式（例如x ² + 5 y + 6）捕获，这些表达式由相加和相乘的变量组成。

对于任何特定问题，例如计算哈密顿路径，您可以构建一个表示它的多项式。例如，您可以用一个变量来表示每个点和边，这样当您添加更多点和边时，您也可以向多项式添加更多变量。

为了证明像计算哈密顿路径这样的算术问题很困难，您需要证明当您添加更多点和边时，相应的多项式需要以指数方式解决更多操作。例如， x ²需要一次操作（将x乘以x ），而x ² + y需要两次操作（将x 乘以 x ，然后加上y ）。操作的数量称为多项式的大小。

但是多项式的大小很难确定。取多项式x ² + 2 x + 1。它的大小似乎为 4（两次乘法和两次加法）。但是多项式可以重写为两个和的乘积，( x + 1)( x + 1)，它的操作更少——仍然是两个加法，但现在只有一个乘法。通常，随着问题的规模化和将更多变量添加到其多项式中，您可以继续简化和缩小其规模。

在 Valiant 工作几年后，计算机科学家找到了一种方法，可以使问题的大小更易于分析。为此，他们提出了一个称为深度的属性，它指定多项式在和和乘积之间切换或交替的次数。例如，多项式x ² + 2 x + 1 的深度为 2，因为它是乘积之和（如x ²和2x ）。相比之下，表达式 ( x + 1)( x + 1) 的深度为三，因为它在技术上与 0 + ( x + 1)( x + 1) 相同，所以它是乘积之和，一其中由总和组成——使整个表达式成为总和乘积的总和。

为了简化多项式，计算机科学家将它们限制为一种形式，其中它们具有称为恒定深度的属性，其中和和乘积的模式不会随着问题的增长而改变。这使得它们的大小更加静态，因为多项式的大小会随着其深度的增加而减小。某个恒定深度（例如深度三）的表示称为公式。

通过研究恒定深度的多项式以及表示它们的图形（称为算术电路），计算机科学家能够取得更大的进步。逐渐地，他们发现了一系列发现，这些发现最终在新工作中达到顶峰。

令人惊讶的深度

Nisan 和 Wigderson 在1996 年的一篇论文中迈出了迈向新结果的第一步。两人专注于一个经常发生的问题，该问题涉及称为矩阵的数字表的乘法。他们以两种方式简化了这个问题。首先，他们用恒定深度的公式来表示它——深度三。其次，他们只考虑了具有某种简单结构的公式，其中每个变量的最大指数为 1——这一特性使它们成为“多线性”。 （实际上，他们只考虑了这种性质略有变化的公式，称为集合多线性公式。）计算机科学家已经知道，某些问题可以转换为这种相对简单的集合多线性结构，代价是次指数它们的规模增加——与指数增长相当的增长率。

Nisan 和 Wigderson 随后表明，随着矩阵的扩大，矩阵乘法问题需要指数级的时间来解决。换句话说，他们证明了一个重要的问题是困难的，在更广泛的证明困难的事业中取得了显着的胜利。然而，他们的结果是有限的，因为它只适用于具有简单的、集合多线性结构的公式。

“如果你在代数复杂性之外工作，那可能对你来说意义不大，”比姆说。

四十多年前，Leslie Valiant 表明，只需要加法和乘法的算术问题可以分为同等难度的类别，现在称为 VNP（用于困难的问题）和 VP（用于更容易的问题）。这些与 NP 和 P 的更一般的复杂性类别平行。

但在接下来的 20 年里，计算机科学家在我们已经看到的基础上，开始更好地理解深度和结构的属性：增加多项式的深度往往会导致其大小减小，并赋予其简单的结构增加它。深度和结构因此与硬度进行了一场拔河比赛。

随着时间的推移，计算机科学家使这两个属性之间的平衡行为变得精确。他们表明，将两个深度级别添加到深度三、集合多重线性多项式可以平衡其集合多重线性结构的大小增益。然后，他们可以对此进行扩展，以表明如果深度 5 的结构化公式需要指数时间，那么具有一般非结构化性质的深度 3 公式也会如此。

新工作的作者随后表明，矩阵乘法问题的深度五组多重线性公式确实以与指数相当的速度增长。通过前面的关系，这意味着一般的深度三公式也需要指数时间。然后他们表明，类似的平衡行为适用于所有深度——不仅仅是三和五。有了这种关系，他们证明了对于同一个问题，任何深度的一般公式的大小都会随着问题的扩展而以指数速度增长。

在这样做的过程中，他们证明了矩阵乘法只要用一个恒定深度的公式表示，就很难，无论该深度是多少。虽然之前深入研究过深度三公式，但我们仍然不知道它们是否难——更深的公式的难（或难）我们一无所知。 “这是一个巨大的突破，”多伦多大学的Shubhangi Saraf说。 “这是过去 30 年来许多美好成果的结合。”

结果提供了对算术问题何时困难的第一个一般理解 – 至少，当它被限制为由恒定深度的公式表示时。研究人员关注的矩阵乘法的具体问题已知是 VP 问题。并且由于已知 VP 问题在不限于恒定深度时相对容易，因此结果将恒定深度限制隔离为硬度的来源。

“该模型受到如此严格的限制，以至于即使在不受限制的世界中应该很容易的事情也会变得困难，”Shpilka 说。

代数复杂性领域的终极问题是，与来自 VP 的问题相比，VNP 问题是否更难。新结果并没有直接说明这一点，因为它只表明恒定深度公式很难。尽管如此，研究人员正在努力以可能让他们找到答案的方式建立在结果的基础上。

“这可能仍然是一个遥远的目标。很可能是这样，”萨拉夫说。 “但这仍然是 [显示] VP 不等于 VNP 的一个重要里程碑。”

对于更大的 P 与 NP 问题，我们现在可以对有一天找到答案的前景更加乐观。毕竟，为了解决我们希望解决的问题，我们首先需要知道哪些是无望的。