论文标题
如果VNP很难，那么方程也是如此
If VNP is hard, then so are equations for it
论文作者
论文摘要
假设永久多项式需要指数尺寸的代数电路，我们表明类VNP没有有效的可计算方程。换句话说，在类VNP中所有多项式的系数向量上消失的任何非零多项式都需要超级多项式大小的代数回路。 在Chatterjee和作者的最新工作中（焦点2020），证明了由多项式组成的VP和VNP的子类具有有界整数系数的多项式，确实具有具有小代数电路的方程式。他们的工作打开了可能将这些结果扩展到所有VP或VNP的可能性。本文的结果表明，假设永久性至少对于VNP的硬度，允许具有较大系数的多项式确实确实会导致方程的电路复杂性发生了显着的爆炸。
Assuming that the Permanent polynomial requires algebraic circuits of exponential size, we show that the class VNP does not have efficiently computable equations. In other words, any nonzero polynomial that vanishes on the coefficient vectors of all polynomials in the class VNP requires algebraic circuits of super-polynomial size. In a recent work of Chatterjee and the authors (FOCS 2020), it was shown that the subclasses of VP and VNP consisting of polynomials with bounded integer coefficients do have equations with small algebraic circuits. Their work left open the possibility that these results could perhaps be extended to all of VP or VNP. The results in this paper show that assuming the hardness of Permanent, at least for VNP, allowing polynomials with large coefficients does indeed incur a significant blow up in the circuit complexity of equations.
