算术电路与 VP/VNP | Codeboy's Blog

形式陈述

电路计算形式多项式

固定一个域 $F$ 。算术电路是一个有限有向无环图：输入门标记变量 $x_i$ 或域常数，内部门是二输入加法或乘法，指定一个输出门。没有除法门；减法可用常数 $-1$ 和加乘表示。中间结果可以供多个后继门共享，整个电路按拓扑序在多项式环 $F[x_1,\ldots,x_v]$ 中求值。[1,2]

本页把规模 $s$ 计为运算门数。另一种口径还计输入节点；对删除无用部分后的二输入电路，总节点数为 $O(s+1)$ ，不改变下面的多项式规模类。每个门的实际输出是一个形式多项式，不能只用它在域元素上的取值函数来替代。

电路的形式次数可逐门估计：常数门为零，变量门为一，加法门取两个前驱的最大值，乘法门取和。实际非零输出多项式的次数不超过这个值，但抵消可使次数下降。VP 定义中的次数限制指输出多项式的实际次数。

多项式族及其指数求和

令 $(f_n)_{n\ge1}$ 是固定域 $F$ 上的多项式族， $f_n$ 的变量数与总次数都由 $n$ 的某个固定多项式控制。若每个 $f_n$ 都存在规模为 $n^{O(1)}$ 的算术电路，则称此族属于 $\mathrm{VP}_F$ 。

这里是非一致电路族：不要求存在一个算法由 $n$ 生成该电路，域常数也可以随 $n$ 选择。下标 $n$ 是族的规模参数，不必恰好等于变量数。

族 $(f_n)$ 属于 $\mathrm{VNP}_F$ ，当且仅当存在多项式有界整数 $m(n)$ 及属于 $\mathrm{VP}_F$ 的族 $(g_n)$ ，使

f_n(x)=\sum_{e\in\{0,1\}^{m(n)}}g_n(x,e). \tag{1}

这里把 $0,1$ 嵌入域 $F$ ，求和在域中进行； $g_n$ 同时把自由变量 $x$ 与见证变量 $e$ 当成不定元，其总变量数、输出次数和电路规模都必须多项式有界。[1,2]

这一定义许可用一个简单多项式描述指数多个求和项，没有声称这些项能被逐一求和而仍只用多项式时间。它也不是“存在某个见证使输出非零”的判定定义。

保持整个多项式的投影

若

f(x_1,\ldots,x_v)=g(a_1,\ldots,a_w), \qquad a_i\in F\cup\{x_1,\ldots,x_v\},

就称 $f$ 是 $g$ 的投影。只允许把目标变量替换为域常数或单个源变量，可以多次使用同一个变量；任意线性表达式或其他多项式不属于此处的替换接口。等号要求在 $F[x]$ 中作为形式多项式成立。

对多项式族，若有多项式有界函数 $t(n)$ ，使每个 $f_n$ 都是 $g_{t(n)}$ 的投影，记为 $(f_n)\le_p(g_n)$ ，称为 p-投影。与电路族一样，投影的逐规模选择不附带一致生成要求。[1,3]

直觉

布尔电路沿门网络传播真假值；算术电路沿类似的网络传播多项式。共享依赖图的结构相同，但运算语义和被保留的信息不同。多项式不仅回答某个输入是否满足性质，还可以保留每个组合对象的权重，以及不同对象贡献的累加。

VP 对应“小电路直接生成整个多项式”，VNP 则允许“用小电路给每个布尔见证赋权，再将全部见证的权重相加”。permanent 是直接的例子：一个置换很容易检查，但它对应的单项式需要与其他所有置换的单项式一起相加。

VP 包含于 VNP 的显式构造

给定 $(f_n)\in\mathrm{VP}_F$ ，加一个见证位 $b$ ，令

g_n(x,b)=(1-b)f_n(x).

其规模和次数仍多项式有界，并且

g_n(x,0)+g_n(x,1)=f_n(x)+0=f_n(x).

所以 $\mathrm{VP}_F\subseteq\mathrm{VNP}_F$ ，任意域上都成立。若直接让 $g_n$ 忽略一个额外见证位，求和会得到 $2f_n$ ；在特征二中甚至变成零。见证的重复编码必须计入求和。

permanent 的完整 VNP 成员性证明

令 $X=(x_{ij})$ 为 $n\times n$ 的独立变量矩阵，定义

\operatorname{per}_n(X)= \sum_{\pi\in S_n}\prod_{i=1}^n x_{i,\pi(i)}.

用 $n^2$ 个布尔见证变量 $Y=(y_{ij})$ 表示候选置换矩阵。先构造“恰有一个一”的多项式

E(t_1,\ldots,t_n)= \sum_{j=1}^n t_j\prod_{k\ne j}(1-t_k).

当输入全为布尔值时：没有一，每项的首因子都为零；恰有一个一，只有对应项为一；至少两个一，每项要么首因子为零，要么包含另一个一所产生的零因子。因此 $E$ 在任意域上都是所需的 $0/1$ 指示器。

同时检查每行与每列，令

B_n(Y)= \prod_{i=1}^n E(y_{i1},\ldots,y_{in}) \prod_{j=1}^n E(y_{1j},\ldots,y_{nj}).

再定义

g_n(X,Y)=B_n(Y) \prod_{i,j=1}^n(1-y_{ij}+y_{ij}x_{ij}). \tag{2}

若 $Y$ 不是置换矩阵， $B_n(Y)=0$ ，此见证贡献零。若 $Y$ 表示置换 $\pi$ ，权重乘积恰为 $\prod_i x_{i,\pi(i)}$ 。每个置换只有一个这样的二进制矩阵编码，所以

\sum_{Y\in\{0,1\}^{n^2}}g_n(X,Y) =\operatorname{per}_n(X). \tag{3}

还需检查资源。一个 $E$ 直接用 $O(n^2)$ 个二输入加乘门实现；共 $2n$ 个这样的检查，连同权重因子，式 (2) 的规模为 $O(n^3)$ 。 $B_n$ 的次数至多 $2n^2$ ，权重乘积次数至多 $2n^2$ ，故总次数至多 $4n^2$ ，总变量数为 $2n^2$ 。因此 $(g_n)\in\mathrm{VP}_F$ ，式 (3) 证明 permanent 族属于 VNP。

不能把 $E$ 换成没有说明的“行和等于一”域运算检查。特征为 $p$ 时， $p+1$ 个一也会加成一；上面的逐项指示器避免了这种模特征混淆。

例子与边界

十六个见证中只有两个有贡献

在 $F=\mathbb Q$ 上取

X=\begin{pmatrix}2&3\\5&7\end{pmatrix}.

四个见证位共有 16 种取法，只有

Y_1=\begin{pmatrix}1&0\\0&1\end{pmatrix}, \qquad Y_2=\begin{pmatrix}0&1\\1&0\end{pmatrix}

通过行列检查。式 (2) 的贡献分别为 $2\cdot7=14$ 和 $3\cdot5=15$ ，所以总和为 $29$ 。其他 14 个见证被 $B_2$ 归零。这是一次加权求和，而非只计算两个有效见证的数量。

一个可以逐项核对的保值投影

在通用 $3\times3$ permanent 中作以下变量与常数替换：

M(x,y,z)= \begin{pmatrix} x&y&0\\ 1&0&z\\ 1&1&x \end{pmatrix}.

六个列排列按字典序给出：

列排列	对应乘积
$(1,2,3)$	$x\cdot0\cdot x=0$
$(1,3,2)$	$x\cdot z\cdot1=xz$
$(2,1,3)$	$y\cdot1\cdot x=xy$
$(2,3,1)$	$y\cdot z\cdot1=yz$
$(3,1,2)$	$0\cdot1\cdot1=0$
$(3,2,1)$	$0\cdot0\cdot1=0$

所以作为形式多项式，

\operatorname{per}_3(M(x,y,z))=xy+xz+yz.

在 $(x,y,z)=(2,3,5)$ 处，两边都为 $31$ 。数值检查辅助发现算错项，正式证明则是上面的全部单项式比较。这个投影保留值、系数与变量关系，强于只保留“零还是非零”。

规模、次数和位成本各自限制什么

从 $x$ 开始重复平方 $n$ 次，以 $n$ 个乘法门得到 $x^{2^n}$ 。这说明小规模并不自动给多项式次数，因此不能省掉 VP 的次数条件。

反过来，在有理数域中从常数 $2$ 开始平方 $n$ 次，再乘 $x$ ，得到 $2^{2^n}x$ ：输出次数只有一，运算数为 $n+1$ ，但系数的二进制长度为 $2^n+1$ 。位复杂度还要支付表示和处理这些长整数的成本；算术门数不能直接当成布尔位模型的运行时间。

在有限域上，形式多项式相等也比所有域点上取值相等更强。例如 $\mathbb F_p[x]$ 中 $x^p-x$ 不是零多项式，却在每个域元素处取零。上述投影定义使用形式恒等，不能靠枚举所有域点来替代它。

推论与应用

小投影怎样传递可计算性

若 $(f_n)\le_p(g_n)$ 且 $(g_n)\in\mathrm{VP}_F$ ，直接把计算 $g_{t(n)}$ 的电路输入叶子按投影替换。不增加运算门，次数也不增加；原规模为 $t(n)$ 的多项式，而 $t(n)$ 又由 $n$ 的多项式控制，因此 $(f_n)\in\mathrm{VP}_F$ 。

若目标在 VNP，写成 $g_{t(n)}(x)=\sum_e h_{t(n)}(x,e)$ ，只替换自由变量 $x$ ，保留见证变量。替换后的 $h$ 仍由多项式规模电路计算，见证长度与次数仍多项式有界，故源族也在 VNP。投影复合仍把每个变量送到一个变量或常数，参数界也经多项式复合保持。

完全性与布尔计数的接口不同

作为已有定理引用，Valiant 的 permanent 完全性断言：当 $\operatorname{char}(F)\ne2$ 时，每个 VNP 族都是 permanent 族的 p-投影。[2,3] 上面的成员性与具体投影没有证明这个对所有 VNP 族的量词。结合刚才证明的闭合性，若此域上 permanent 族属于 VP，就有 VP = VNP。

特征二中 $-1=1$ ，行列式的置换符号全部消失，permanent 与 determinant 成为同一个形式多项式；不能把带有特征限制的完全性定理原样移到这里。式 (3) 的成员性证明本身仍然成立。

#P研究位串输入上的非负整数计数函数，VP/VNP 研究固定域上的非一致多项式族。一个 $0$ – $1$ 矩阵的整数 permanent 可以数完美匹配，放到特征 $p$ 的域中则只得到该整数模 $p$ 的像。布尔计数中的多项式时间 Turing 归约，也不同于本页只替换常数与变量的 p-投影。使用相同表达式，不等于两种复杂性模型已有相同结论。

参考资料

[1] Christian Ikenmeyer and Abhiroop Sanyal, A Note on VNP-Completeness and Border Complexity, 2021，§2.1，pp. 3–4：形式多项式族、非一致性、VP 与 p-投影；其规模计全部节点。
[2] Peter Bürgisser, Completeness Classes in Algebraic Complexity Theory, 2024，Definitions 2.1、2.15、2.25，Remark 2.10 及 Theorem 2.29：运算门口径、现代 VP/VNP 定义与带特征限制的完全性。本文采用其二输入无除法模型。
[3] Leslie G. Valiant, Completeness Classes in Algebra, STOC 1979，pp. 249–261，§§1、3–4：投影、permanent 的见证描述和 Theorem 2。原文的公式表述与现代电路定义有所不同；式 (2) 是本页展开的直接成员性构造。

形式陈述 ​

电路计算形式多项式 ​

多项式族及其指数求和 ​

保持整个多项式的投影 ​

VP 包含于 VNP 的显式构造 ​

permanent 的完整 VNP 成员性证明 ​

十六个见证中只有两个有贡献 ​

一个可以逐项核对的保值投影 ​

规模、次数和位成本各自限制什么 ​

小投影怎样传递可计算性 ​

完全性与布尔计数的接口不同 ​

反向链接