P/NP问题是计算复杂性领域中迄今为止未解的问题。人们一直试图找到这个问题的答案：“我们能否在合理的时间内高效地解决所有的计算问题？”什么是合理时间？事实上，宇宙终结前能解决的问题，都算在合理的时间内。然而，许多问题似乎难以在合理的时间内解决，需要对其难度进行数学证明。2021年的一项研究回答了这些问题，该研究证实很大一部分问题难以有效解决。华盛顿大学的PaulBeame评价这项研究说：“就像攀登一座山，这项研究是计算理论研究道路上的一个落脚点。”该研究的三位研究人员：计算机科学家SrikanthSrinivasan（左）、NutanLimaye（右上）和SébastienTavenas。研究中考虑的问题仅涉及加法和乘法，但是当这些问题被限制为以特定方式解决时（一些加法和乘法的交替模式），它们变得非常困难。令人惊讶的是，该研究没有使用新的框架或工具；相反，作者设法绕过了普林斯顿高等研究院数学教授Wigderson与耶路撒冷希伯来大学的NoamNisan合作数十年工作中所描述的数学。障碍。“我们意识到有一种非常简单的方法可以绕过这个障碍，”其中一位研究人员、丹麦奥胡斯大学的SrikanthSrinivasan说。“而且，如果用这种简单的方法可以做到我们认为不可能的事情，那么一定有更好的方法。”重要问题计算机出现后，科学家们发现计算机算法可以解决很多问题，但有时这些算法花费的时间太长——比实际计算的时间还长。大小。例如，在图中，一个重要的问题是确定是否存在哈密顿路径，即通过每个顶点恰好一次的路径。增加顶点（和边）的数量应该花费更长的时间来确定是否存在这样的路径，但即使是最好的算法也会随着图尺寸的增加而花费指数级的时间，这使得解决这个问题变得不现实。计算机科学家试图证明，任何以某种方式有效解决一类问题中的一个难题的算法都可以转化为一个解决方案其他类似hardproblem，他们称之为NPproblems，当然也有很多看似简单的问题，其实并不需要oo很多时间解决。其中很多问题在某种意义上也是等价的，这类问题称为P问题。他们认为NP问题确实比P问题更难，而且NP问题永远无法有效解决。但在没有证据的情况下，这种想法可能是错误的。于是计算机科学家开始寻找方法来证明NP问题确实更难，这就需要证明NP问题必须用指数时间来解决，但要证明这一点并不容易。“难”有多难？想象一组只需要加法和乘法的特定问题。例如，给定一组点，仅通过加法和乘法就可以根据关于这些点的数据计算出所有可能的哈密顿路径（如果有的话）。随着问题规模的增加，一些算术问题（例如计算哈密顿路径）需要更多时间。1979年，哈佛大学的LeslieValiant证明了很多算术题在“难度”上是等价的，而另一些在“不难”上是等价的。计算机科学家后来以他的名字命名了这两类问题——分别是VNP和VP。与Pvs.NP问题一样，我们无法证明VPN问题的难度，我们只知道VPN问题比NP问题更难，因为它建立在后者之上，例如计算路径首先需要判断路径是否存在。“它比NP更难，所以应该更容易证明它很难，”Shpilka说。在随后的几十年里，计算机科学家在VPvs.VNP上取得的进展比在Pvs.NP上取得的进展要大得多，但其中大部分仅限于Valiant创建的称为代数复杂性的方法。子领域。在Limaye、Srinivasan和Tavenas最近的工作之前，他们仍然很难判断是否存在一般意义上的算术问题。调整多项式这项新工作有助于探索计算机科学家思考加法和乘法问题的方式。在数学上，这些问题可以完美地写成多项式的形式（例如x^2+5y+6），它由相加和相乘的变量组成。对于任何特定问题，例如计算哈密顿路径，您可以构造一个多项式来表示它。例如，您可以用一个变量表示每个点和边，这样随着添加更多的点和边，更多的变量可以添加到多项式中。为了证明诸如计算哈密顿路径之类的算术问题是困难的，需要证明随着添加更多的顶点和边，对应的多项式需要以指数方式增加更多的运算才能求解。例如，x^2需要一次操作(x*x)，而x^2+y需要两次操作（x*x后跟y）。运算次数称为多项式的大小。但是多项式的大小很难确定。例如多项式x^2+2x+1。它的大小似乎为4（两次乘法和两次加法），但多项式可以重写为两个和的乘积，(x+1)(x+1)，它需要更少的操作数-两次加法，一次乘法。通常，数学变换可以帮助简化和减小问题的大小，因为它的大小会增加并且更多的变量会添加到多项式中。Valiant工作几年后，计算机科学家找到了一种方法，使问题的规模更易于分析。为此，他们提出了一个名为“深度”的属性，该属性指定多项式在和与积之间切换或交替的次数。例如，多项式x^2+2x+1的深度为2，因为它是乘积之和（如x^2和2x）。相反，表达式(x+1)(x+1)的深度为3，因为它与0+(x+1)(x+1)具有相同的深度，计算为乘积之和。为了简化多项式，计算机科学家将它们限制为固定形式，具有称为“恒定深度”的属性，其中求和和乘积的模式不会随着问题的增长而改变。这使得它们的大小更加固定，多项式的大小随着深度的增加而减小。某个恒定深度的表达式称为公式。恒定的深度允许在多项式的研究中取得更多进展。“深度”的魔力1996年，Nisan和Wigderson的一篇论文着重于解决矩阵乘法问题，他们以两种方式对其进行了简化。首先，他们用一个常量深度公式来表示它——深度为3。其次，他们只考虑了结构有些简单的公式，其中每个变量的最大指数为1，这使得原始问题成为“多线性”问题。计算机科学家发现，某些问题可以转化为相对简单的集合多线性结构，但代价是多项式的大小呈次指数增长（相当于指数增长率）。Nisan和Wigderson随后表明，随着矩阵规模的增长，矩阵乘法问题的求解时间呈指数级增长。换句话说，他们证明了一个重要的问题是难的，并且努力证明一类问题是难的。然而，他们的结果仅适用于具有简单、整体多线性结构的公式。LeslieValiant增加多项式的深度往往会减小其大小。随着时间的推移，计算机科学家改进了这两个属性之间的权衡。他们表明，将两个深度级别添加到深度3，集成多重线性多项式可以平衡其集成多重线性结构的大小增益。如果深度5的结构化公式需要指数时间，那么具有一般非结构化属性的深度3的公式也是如此。SrikanthSrinivasan等人的新作品。表明矩阵乘法问题的深度5集多线性公式确实呈指数级扩展。这意味着一般深度为3的公式也需要指数时间。然后他们证明了类似的模式适用于所有深度（不仅仅是3和5）。通过这种关系，他们表明对于同一个问题，任何深度的通式的大小都随着问题的大小呈指数增长。他们还表明，无论深度是多少，都很难在恒定深度公式中表达矩阵乘法。该研究的结果首次提供了对算术问题何时“困难”的一般理解——当它不能用一个恒定深度的公式来表述时。矩阵乘法的具体问题称为VP问题。并且众所周知，VP问题在不限制深度不变的情况下相对容易，所以事实证明，深度不变是问题“难”的根源。VPN问题是否比VP问题更难？新的结果没有直接表明这一点，它们只表明恒定深度公式很难。但这仍然是证明VPN问题不能等同于VP问题的重要里程碑。对于更大的P与NP问题，我们现在可以更加乐观地认为有一天我们会找到答案。毕竟，要解决难题，首先要知道哪些方向是无望的。
