布尔电路

布尔电路把一次性计算展开为空间中的无环数据依赖图：每个门只执行固定局部函数，所有输入一旦给定，值便沿有向边传播。图的宽度体现并行，最长依赖链体现延迟；共享子表达式可以只计算一次并供多个后继门复用，这使电路不同于纯公式树。与会反复读写工作带的图灵机相比，单个电路只处理固定长度输入，因此研究的是“每个长度一张专用硬件图”。

半加器对输入 $(a,b)$ 输出和位 $s=a\oplus b$ 与进位 $c=a\wedge b$。输入 $11$ 时输出 $(s,c)=(0,1)$，解释为二进制数 $10$；输入 $10$ 时为 $(1,0)$。它说明多输出电路的输出顺序也是接口的一部分。若基础门只有 AND/OR/NOT，可令 $s=(a\vee b)\wedge \mathrm{\neg }(a\wedge b)$，并把中间值 $a\wedge b$ 同时供和位与进位使用。另一个例子是函数 $(x_1\wedge x_2)\vee (\mathrm{\neg }{x}_1\wedge x_3)$：它可由两个 AND、一个 NOT 和一个 OR 门实现，且 $x_1$ 可扇出到两个门。公式则把每次输入文字出现也画成独立叶，使非根节点都只有一个父节点；相同变量可以标在多片叶上。这个树形表示无法共享内部子表达式，可能比一般电路更大。

若要求 fan-in 为 $2$，对 $n\ge 1$，一个 $n$ 输入 AND 可用树形门网实现，深度为 $\lceil {\log }_{2}n\rceil$，其中 $n=1$ 时直接输出唯一输入；零输入 AND 按空合取约定由常量真表示。若允许无界 fan-in，深度定义会改变。电路还必须无环，否则门值可能没有唯一的静态解释；带反馈的硬件应建模为时序电路或状态机。单个长度 $n$ 的任意真值函数总有有限电路，但它只处理该长度；语言复杂性真正考察随 $n$ 增长的规模、深度和电路族可生成性。

布尔电路是硬件设计、逻辑综合、SAT、并行算法与非一致复杂性的共同基础。命题逻辑公理库命题逻辑Propositional logic · Propositional calculus研究命题如何通过逻辑联结词组合以及公式在真值赋值下何时成立。提供门的语义，有向无环图公理库有向无环图Directed acyclic graph · DAG不含有向环的有向图。提供结构；规模与深度公理库电路规模与深度Circuit size and depth分别计数门数和最长输入到输出路径长度的电路资源度量。分别衡量工作量和并行时间，一致性公理库电路族一致性Circuit family uniformity要求输入长度 n 对应电路可由统一算法有效生成的条件。则说明一族电路能否由统一算法生成。

同态自举公理库同态自举刷新Bootstrapping for FHE把旧密文作为公开常量、旧私钥位作为新密钥下的密文，求值解密电路以刷新表示，并区分功能余量、独立密钥链和循环安全。提供一个深度必须精算的应用：把旧密文固定为公开常量，将私钥位的加密作为变量，求值解密电路并为下一门留出余量。这里换门基或引入无界扇入会改变实际预算，不能只凭“解密是多项式时间”就断言方案能自举。

沿着“每个输入长度使用一张电路”的视角，P/poly公理库非一致电路类 P/polyP/poly · Nonuniform polynomial size由每个输入长度各自选取的多项式规模布尔电路族判定、无需统一生成算法的语言类。刻画多项式规模但不要求一致生成的电路族，AC⁰公理库AC⁰AC0 · AC^0 · Constant-depth unbounded-fan-in circuits由多项式规模、常数深度、无界扇入 AND/OR 门电路族计算的布尔函数类。进一步限制为常数深度、无界扇入。另一条路线是把门的布尔关系变成域上的低次多项式；这种算术化公理库算术化Arithmetization把布尔关系嵌入有限域低次多项式，使离散正确性声明可由随机代数恒等式检查。是代数化验证与交互式证明的入口。

同一布尔函数还可置于不同资源模型中。查询复杂度公理库确定性与随机查询复杂度Deterministic query complexity · Randomized query complexity以决策树和量词定义确定性、允许错误与零错误查询成本，用 OR、奇偶与带间隔多数解释随机化的作用。只数为确定输出而读取的输入位，电路规模则数整张非自适应计算图中的门；二者没有由定义得到的等式。把输入位分给两方并插入 gadget 后，lifting 定理公理库通信复杂度 lifting 定理Communication complexity lifting theorem · Query-to-communication lifting用两方 gadget 替换外层函数的每个输入位，把查询树下界提升为组合通信函数及其相关模型下界。可在满足假设时把决策树下界提升为通信下界，进而服务某些电路下界。性质测试公理库性质测试模型Property testing model · Property testing明确 oracle、距离和承诺间隔，用测试算法与下界区分局部违规、全局距离、容忍性和查询成本。又只要求区分满足性质与远离性质的真值表或函数 oracle，不能把测试器的少量查询直接解释为一个计算全部输入的微型电路。

算术电路与 VP/VNP公理库算术电路与 VP/VNPArithmetic circuit · VP and VNP · 算术电路固定域上的形式多项式电路、VP/VNP 与保值投影，包含 permanent 的显式见证求和和代数成本边界。把同一无环门网络改为域上的加乘运算，研究形式多项式族。该页用置换矩阵见证证明 permanent 的 VNP 成员性，并给出只替换常数与变量、保持整个多项式的投影。