低深度代数电路的超多项式下界I:概述

每一个多元多项式P(x_1，…，x_n)都可以写成一个单项的和，即变量和场常数的乘积的和。一般来说，这样一个表达式的大小是P中系数非零的单项数。

如果我们增加另一层复杂性，并考虑(变量和字段常量)表达式的和的乘积的和，会发生什么?现在，如何证明给定多项式P(x_1，…，x_n)没有小表达式变得不清楚了。在这个结果中，我们正好解决了这个问题。

更准确地说，我们证明了某些显式多项式没有多项式大小的“Sigma-Pi-Sigma”(和的乘积的和)表示。对于所有“恒深度”表达式，我们也可以对Sigma-Pi-Sigma-Pi、Sigma-Pi-Sigma-Pi- sigma等等给出类似的结果。