算术化

形式陈述 ​

选取有限域公理库有限域Finite field · Galois field底层集合有限的域。 $\mathbb{F}$，把布尔值嵌入为 $0,1\in \mathbb{F}$。对布尔输入，基本联结词可替换为

$$\mathrm{\neg }x\mapsto 1-x,x\wedge y\mapsto xy,x\vee y\mapsto x+y-xy.$$

逐门替换可把布尔电路公理库布尔电路Boolean circuit由逻辑门构成的有限无环有向图，计算布尔函数。或公式转成多项式环公理库多项式环Polynomial ring系数来自给定环、以形式不定元构造的多项式集合。中的表达式，并在 $\{0,1{\}}^n$ 上保持函数值。任意布尔函数还存在唯一的多线性扩展

$$\tilde{f}(x)=\sum _{a\in \{0,1{\}}^n}f(a)\prod _{i:a_i=1}{x}_i\prod _{i:a_i=0}(1-x_i),$$

它在 Boolean cube 上与 $f$ 一致，每个变量次数至多一。算术化的算法不变量应同时跟踪变量数、单变量次数或总次数、域大小与表达式求值成本；交互证明中常需在每层运算后重新多线性化，避免直接展开让 degree 指数增长。

直觉 ​

真假关系公理库命题逻辑Propositional logic · Propositional calculus研究命题如何通过逻辑联结词组合以及公式在真值赋值下何时成立。变成低次多项式后，验证者不必逐个检查指数多个布尔点，而可要求证明者承诺一个代数对象，再在随机域点检查它是否与先前承诺相容。不同低次多项式只能在有限数量的随机点偶然相等，随机挑战便把全局谎言压缩成可检测的局部不一致。

算术化不是把“真”改写成更漂亮的符号。它的价值来自低次数、可高效求值和域上随机性三者同时成立；如果多项式次数失控，随机检查的 soundness 也会失去意义。

例子与边界 ​

公式 $(x\vee y)\wedge \mathrm{\neg }z$ 可写成

$$p(x,y,z)=(x+y-xy)(1-z).$$

对任意 $x,y,z\in \{0,1\}$，$p$ 恰取对应布尔值。例如 $x=1,z=0$ 时第一因子为 $1$，而 $z=1$ 时第二因子把结果归零。这个核对使用了输入为 bit 的约束。

多项式 $x$ 与 $x^2$ 在 $\{0,1\}$ 上表示同一布尔函数，却不是形式多项式恒等；在一般域点 $r$ 上通常有 $r\ne r^2$。因此“在 Boolean cube 上相同”和“在 ${\mathbb{F}}^n$ 上相等”必须区分，多线性化相当于使用关系 $x_i^2=x_i$ 选择规范代表。

直接沿深电路把乘法门展开，degree 可能随层数成倍增长。Sum-check 或 IP 证明若声称保持低次，必须给出重新低次数化步骤，而不能沿用最初每门次数小的局部事实。域特征也会改变系数，例如特征二中减号与加号相同，所有公式仍需按所选域复核。

推论与应用 ​

算术化支撑 sum-check、低度测试、交互证明和部分 PCP 构造。它把逻辑量词、约束满足和电路求值转成关于多项式和指数和的声明，随后才可使用随机域点降低验证成本。

不同应用需要不同编码：逐门多项式适合展示语义，多线性扩展适合把真值表推广到域，低度扩展则兼顾编码距离与局部查询。选择编码时应先确定后续协议需要检查什么，而不是把这些扩展混为同一对象。

参考资料

• Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan, “Algebraic Methods for Interactive Proof Systems,” Journal of the ACM 39(4), 1992, pp. 859–868.
• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009, Ch. 8.