ACM通信
研究突出了
技术展望:低深度算法电路
使用加法和乘法(可能还有除法)的算术运算来计算多项式(我们将在整个过程中假设一个域的特征为零或足够大)，当然就像通过逻辑门计算布尔函数一样自然，并捕获了许多自然的重要任务，包括傅里叶变换、线性代数、矩阵计算和在许多设置中出现的更一般的符号代数计算。算术电路是理解此类任务计算复杂性的天然计算模型，就像布尔电路是布尔函数的计算模型一样。代数结构和数学工具的出现是几个世纪以来代数研究提供的，这给人们带来了希望:理解算术电路将比理解布尔电路更快更容易。虽然我们对算术电路有了更多的了解，但它们的能力还远远没有被理解，特别是Valiant提出的布尔P与NP问题的算术模拟VP vs. VNP8是完全开放的。
在过去的几年里，我们对算术电路的理解发生了一场革命。令人惊讶的新上界，结合新的强大的证明下界的技术，使我们认识到非常浅层的电路在捕捉该领域的长期目标方面的神秘重要性，并以罕见的精确度在这个模型中精确地确定自然问题的复杂性。这些发展重新燃起了希望，并给出了一个具体的方案，使Valiant的职业VP和VNP可能分离。以下古普塔等人关于“深度3的鸿沟”的论文是这种新认识的顶点之一。现在，我将简要解释“鸿沟”现象，以及本文作者详细阐述的其中一些发展。
20世纪80年代关于等深度布尔电路的一系列重要工作很好地描述了它们的局限性，包括在对称函数等极其简单的函数上存在紧密的指数下界。其基本信息是，恒定深度(和多项式大小)是一种非常弱的算法。奇怪的是(特别是在足够大的域上)，这种直觉在算术电路中完全失效。在1980年，Ben-Or已经做了一个重要的简单观察，即对称多项式可以通过二次元大小公式在深度-3中计算!证明这个简单模型的指数下界的挑战开始了。Nisan-Wigderson在进一步的限制(如同质性)下证明了这种界限，6他将偏导数和随机约束的重要技术引入到算术电路的研究中。虽然最佳的一般下界是二次的(匹配对称多项式的Ben-Or结果)，但仍然有一种信念认为，恒定深度是一个弱模型，我们应该很容易证明更好的下界，对于更复杂的函数，如永久函数和甚至行列式。然而，十多年来一直没有这样的进展。
阿格拉瓦尔和维奈发表了一篇令人惊讶且有影响力的论文，1他们称之为“深度4的裂口”出现在2008年。它的明确信息是:证明(即使是齐次)深度-4电路的下界和证明一般电路的下界一样困难(或者，对乐观主义者来说，同样有用)。延续Valiant、Skyum、Berkowitz和Rackoff著名的深度缩减技术，9本文(加上Tavenas和Koiran的改进)证明了任何大小的算术电路年代计算学位d多项式也可以通过一个齐次深度-4大小的电路来计算
．例如，证明一个次指数
计算永久上的下界n×n矩阵，在这样一个弱的恒定深度电路上，会将VP和VNP分离!但是回想一下，即使在深度3中我们也陷入了困境。
虽然我们对算术电路有了更多的了解，但它们的能力还远未被理解。
接下来，一系列的论文，主要是由当前作者的子集和其他一些人使我们非常接近这个目标!他们利用源自希尔伯特交换代数工作的代数几何的深刻思想和结果，将偏导数的方法扩展到更强的“移位偏导数”，并结合包括非常精细的组合分析在内的其他思想，能够到达裂谷，但不能跨越它。更准确地说，他们证明了
或者是行列式和永久式。注意，对于行列式，这个下界是紧的，因此更改这个表达式中的to将把两者分开，从而将VP与VNP分开。
深度4到此为止。本文证明了同样的鸿沟实际上存在于深度为3的区域，至少在有理数等特征为0的域上存在。更准确地说，如上所述，每一种尺寸年代计算次多项式的算术电路d可以通过深度-3大小的电路计算吗(不幸的是，它们不再是齐次的，实际上有很大的度数)。很难向非专家解释为什么这是如此出乎意料，但和以前一样，它传递了同样的信息:证明即使在深度3的算法电路中，计算永久函数的下界也会将VP和VNP分开。
同样，对于乐观主义者来说，这意味着我们非常接近解决该领域的一个主要目标。对于悲观主义者来说，这可能只是说明了深度-3电路有多强，证明它们的下界是多么无望。我是乐观主义者。据我们所知，在算术设置中，我们没有“自然证明”或“相对化”的障碍(也就是借口)，这似乎解释了我们迄今为止未能证明布尔设置中的下界。此外，算术设定正在兑现提供数学技术的承诺，这可能有助于解决它的主要问题，正如这里的工作线所表明的。当然，另一个标志是Mulmuley和Sohoni的几何复杂性理论(GCT)方法，5该研究基于不变理论和表征理论，从不同的方向探讨了VP和VNP问题。的确，人们发现了这两种方法之间的一些关系和联系，纯数学家对这些计算复杂性问题日益增长的兴趣令人鼓舞。
随着我们对计算复杂度的期望越来越高，算术复杂度的研究与该领域其他看似不同的子领域之间存在着无数的联系。伪随机性的一个重要联系，特别是去随机化多项式同一性检验(PIT)的概率算法与Kabanets和Impagliazzo发现的算术下界之间的密切关系。4随后，Dvir和Shpilka2启动了一个程序来理解非常浅的电路的这个问题，一方面连接到局部可解码和可纠正的代码，另一方面连接到组合几何(主要是关联理论)。这导致了一长串的论文，为越来越多的低深度和其他电路模型获得新的下界和新的身份测试算法。Grochow和Pitassi最近建立了另一个令人兴奋的联系3.在算术复杂度，PIT和证明复杂度之间，什么必然会发展并可能导致该领域的下界。
让我用一个谜语来结束:布尔电路上的深度-3下界是否会像在算术设置中那样，导致“真正的”下界?是的!Valiant的肯定答案7早于所有这些发展。在本文中Valiant证明了任何需要exp(n深度-3布尔电路不能用线性大小的对数深度电路计算。布尔电路中最先进的下界是如此可怜，以至于自Valiant的论文以来，后者仍然是它的主要目标之一，并且可以通过足够强的深度-3下界来实现。
继续证明真正的下限!
参考文献
1.阿格拉瓦尔，M.和维奈，V.算术电路:一个深四的鸿沟。在计算机科学基础年度研讨会论文集。Ieee, 2008, 6775。
2.Dvir, Z.和Shpilka, A.深度3电路的具有两个查询和多项式同一性测试的局部可解码码。SIAM计算学报36， 5(2007)， 14041434。
3.Grochow, J.等。电路复杂度，证明复杂度，多项式同一性测试。在第55届IEEE计算机科学基础年会论文集。电子学报，2014，(3):379 - 379。
4.卡巴内茨V.和Impagliazzo R.恒等检验意味着证明电路的下界。第一版。复杂性13， 12(2004)， 146。
5.几何复杂性理论I:一种方法Pvs。NP以及相关的问题。康普特。31， 2(201)， 496526。
6.通过偏导数的算术电路的下界。计算复杂度6， 3(1996)， 217234。
8.Valiant L.G.完备性代数类。在十一届会议记录thACM计算理论年度研讨会，(1979)， 249261。
9.勇敢的。l.g.， Skyum, S.， Berkowitz, S.和Rackoff, C.使用少量处理器的多项式的快速并行计算。SIAM计算学报12， 4(1983)， 641644。
数字图书馆是由计算机协会出版的。版权所有©2017 ACM, Inc.
没有找到条目