算术电路复杂性

算术电路是指在计算复杂性理论中，计算多项式的一个计算模型。对于一个给定的域F，一个算术电路计算一个在F[x₁,...,x_n]中的多项式。它一般被认为是计算多项式最自然的计算模型，并可以看作是存储多项式的数据结构。而证明某些多项式如积和式在算术电路下需要操作步骤的下界问题是计算复杂性理论中的重要的未解决的问题。

定义

算术电路是一个有向无环图，除拓扑排序为极大的元素的出度为0外，其它结点出度均为1。所有的结点入度为0或者2。入度为0的结点称为叶结点，入度为2出度为1的结点称为中间结点，入度为2出度为0的结点为输入结点（输入结点不一定唯一）。叶结点被一个不定元或一个域中的元素标记，而中间结点和输出结点被‘+’或者‘${\displaystyle \times }$ '标记。定义叶结点计算的多项式为其标记，然后按照拓扑排序，定义非叶结点计算的多项式为其标记的操作符对两个孩子计算的多项式进行操作得到的结果。

计算多项式的其它模型

关于计算多项式，除了算术电路外还有其它的计算模型，包括稀疏表示、稠密表示和算术算式（formula）。从下面的定义可以看出，它们形成了一定的层次关系。这些计算模型也可以看作是存储多项式的数据结构。作为这四种表示中表达力最强的模型，算术电路有着许多优点，如在取最大公因子、提取因子和取一次偏导等操作下具有封闭性。相对的，稀疏表示在提取因子的操作下不封闭（即存在一个多项式，其包括较少数目的单项式，而它的某个因子包含较大数目的单项式）。下面简单介绍这几种表示。

稠密表示

对于一个n个变量，度数限制为不超过d的多项式，将其所有的${\displaystyle n+d \choose d}$ 个单项式的系数按照单项式的某顺序列出（如单项式的字典序），我们就得到了该多项式的稠密表示。容易看到，稠密表示在计算多项式加减上是最方便的。

稀疏表示

对于一个单项式${\displaystyle x_{1}^{i_{1}}x_{2}^{i_{2}}\dots x_{n}^{i_{n}}}$ ，可以依次将${\displaystyle x_{1}}$ 到${\displaystyle x_{n}}$ 的指数列出如${\displaystyle (i_{1},i_{2},\dots ,i_{n}}$ ，称为该单项式的指数向量。那么对于一个n个变量的多项式，将其所有的单项式的系数连同指数向量一起列出，我们就得到了多项式的稀疏表示。这里的稀疏是相对于上面的稠密表示而言：两者的区别在于，稠密表示将所有可能的单项式的系数一起列出，而不论其是否为0；稀疏表示只列出系数非0的单项式的系数，而代价在于需要同时列出指数向量。

稀疏表示与算术电路相比有趣的一点在于，如果一个多项式有一个“小”的稀疏表示（只有少数的单项式系数非0），它的因子可能有很“大”的稀疏表示（有很多系数非0的单项式）。当然一个简单的例子是${\displaystyle x^{n}-1=(x-1)(x^{n-1}+x^{n-2}+\dots 1)}$ 。而当我们用多项式来作为小的标准时，举例为^[1]：考虑${\displaystyle \mathbb {Q} [x_{1},\dots ,x_{n}]}$ 。令${\displaystyle f_{n}(x)=x^{n-1}+x^{n-2}+\dots +1}$ ，及

${\displaystyle g_{n}=\prod _{i=1}^{n}f_{n}(x_{i}),}$ 

${\displaystyle h_{n}=\prod _{i=1}^{n}(x_{i}-1),}$ 

${\displaystyle p_{n}=h_{n}(g_{n}+n)}$ 

那么${\displaystyle g_{n}+n}$ 是p_n的一个不可约因子，有${\displaystyle n^{n}=(2^{n})^{\log n}}$ 个单项式。而${\displaystyle p_{n}}$ 有${\displaystyle 2^{n}+O(n^{2})}$ 个因子。于是可以看到${\displaystyle g_{n}+n}$ 的单项式的数目不是${\displaystyle p_{n}}$ 的单项式的数目，变量的个数n，度数${\displaystyle n^{2}}$ 的多项式，也就是说是一个很大的数目。

算术算式

基本结论

齐次化（homogenize）

VP和VNP

VP=VNC₂

VP在因子提取下封闭

VNP完全

积和式下界问题

参考

1. von zur Gathen, Joachim, Factoring sparse multivariate polynomials, Foundations of Computer Science, Annual IEEE Symposium on, Los Alamitos, CA, USA: IEEE Computer Society, 1983  使用|accessdate=需要含有|url= (帮助)