算術電路複雜性

算術電路是指在計算複雜性理論中，計算多項式的一個計算模型。對於一個給定的域F，一個算術電路計算一個在F[x₁,...,x_n]中的多項式。它一般被認為是計算多項式最自然的計算模型，並可以看作是存儲多項式的資料結構。而證明某些多項式如積和式在算術電路下需要操作步驟的下界問題是計算複雜性理論中的重要的未解決的問題。

定義

算術電路是一個有向無環圖，除拓撲排序為極大的元素的出度為0外，其它結點出度均為1。所有的結點入度為0或者2。入度為0的結點稱為葉結點，入度為2出度為1的結點稱為中間結點，入度為2出度為0的結點為輸入結點（輸入結點不一定唯一）。葉結點被一個不定元或一個域中的元素標記，而中間結點和輸出結點被『+』或者『$\times$'標記。定義葉結點計算的多項式為其標記，然後按照拓撲排序，定義非葉結點計算的多項式為其標記的操作符對兩個孩子計算的多項式進行操作得到的結果。

計算多項式的其它模型

關於計算多項式，除了算術電路外還有其它的計算模型，包括稀疏表示、稠密表示和算術算式（formula）。從下面的定義可以看出，它們形成了一定的層次關係。這些計算模型也可以看作是存儲多項式的資料結構。作為這四種表示中表達力最強的模型，算術電路有著許多優點，如在取最大公因子、提取因子和取一次偏導等操作下具有封閉性。相對的，稀疏表示在提取因子的操作下不封閉（即存在一個多項式，其包括較少數目的單項式，而它的某個因子包含較大數目的單項式）。下面簡單介紹這幾種表示。

稠密表示

對於一個n個變量，度數限制為不超過d的多項式，將其所有的$n+d \choose d$個單項式的係數按照單項式的某順序列出（如單項式的字典序），我們就得到了該多項式的稠密表示。容易看到，稠密表示在計算多項式加減上是最方便的。

稀疏表示

對於一個單項式$x_{1}^{i_{1}}x_{2}^{i_{2}}\dots x_{n}^{i_{n}}$，可以依次將$x_{1}$到$x_{n}$的指數列出如$(i_{1},i_{2},\dots ,i_{n}$，稱為該單項式的指數向量。那麼對於一個n個變量的多項式，將其所有的單項式的係數連同指數向量一起列出，我們就得到了多項式的稀疏表示。這裡的稀疏是相對於上面的稠密表示而言：兩者的區別在於，稠密表示將所有可能的單項式的係數一起列出，而不論其是否為0；稀疏表示只列出係數非0的單項式的係數，而代價在於需要同時列出指數向量。

稀疏表示與算術電路相比有趣的一點在於，如果一個多項式有一個「小」的稀疏表示（只有少數的單項式係數非0），它的因子可能有很「大」的稀疏表示（有很多係數非0的單項式）。當然一個簡單的例子是$x^{n}-1=(x-1)(x^{n-1}+x^{n-2}+\dots 1)$。而當我們用多項式來作為小的標準時，舉例為：考慮$\mathbb {Q} [x_{1},\dots ,x_{n}]$。令$f_{n}(x)=x^{n-1}+x^{n-2}+\dots +1$，及

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

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

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

那麼$g_{n}+n$是p_n的一個不可約因子，有$n^{n}=(2^{n})^{\log n}$個單項式。而$p_{n}$有$2^{n}+O(n^{2})$個因子。於是可以看到$g_{n}+n$的單項式的數目不是$p_{n}$的單項式的數目，變量的個數n，度數$n^{2}$的多項式，也就是說是一個很大的數目。

基本結論

齊次化（homogenize）