布尔电路

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

半加器用 XOR 与 AND 产生和位与进位；若基础门只有 AND/OR/NOT，XOR 可用常数多个门实现。另一个例子是函数 $(x_1\wedge x_2)\vee (\mathrm{\neg }{x}_1\wedge x_3)$：它可由两个 AND、一个 NOT 和一个 OR 门实现，且 $x_1$ 可扇出到两个门。公式则是扇出为一的树状电路，可能因无法共享子表达式而更大。

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

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

沿着“每个输入长度使用一张电路”的视角，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在坐标访问模型中分别定义确定性、零误差随机和有界误差随机查询复杂度，并固定最坏与期望口径。只数为确定输出而读取的输入位，电路规模则数整张非自适应计算图中的门；二者没有由定义得到的等式。把输入位分给两方并插入 gadget 后，lifting 定理公理库通信复杂度 lifting 定理Communication complexity lifting theorem · Query-to-communication lifting用两方 gadget 替换外层函数的每个输入位，把查询树下界提升为组合通信函数及其相关模型下界。可在满足假设时把决策树下界提升为通信下界，进而服务某些电路下界。性质测试公理库性质测试模型Property testing model · Property testing通过少量 oracle 查询区分完全满足性质的对象与到该性质至少相距 ε 的对象，并允许 gap 内行为任意。又只要求区分满足性质与远离性质的真值表或函数 oracle，不能把测试器的少量查询直接解释为一个计算全部输入的微型电路。