46.电路复杂度

title: 46. 电路复杂度 tags: zk complexity theory boolean circuits circuit-SAT circuit complexity WTF zk 教程第 46 讲：电路复杂度 这一讲，我们将介绍电路复杂度，着重介绍布尔电路和算术电路的概念，它们对理解零知识证明系统很重要。 布尔电路 布尔电路不同于我们在中学物理学习的电路，是由逻辑门（AND、OR、NOT）和连线组成的有向无环图（DAG），用于计算布尔函数。 1.1 定义 布尔电路 $C$ 是一个有向无环图，其中： 输入节点：代表输入变量。 内部节点：代表逻辑门，如AND、OR、NOT，分别用符号 $\wedge$, $\vee$, $\neg$ 表示。 输出节点：代表电路的输出。 举个例子，下面的布尔电路有3个输入节点 $(x1, x2, x3)$，计算的布尔函数为： $$\phi = \neg{(x1 \wedge x2)} \wedge ((x2 \wedge x3) \vee \bar{x3})$$ 当输入为 $(0, 1, 0)$ 时，布尔电路的输出为 $1$。 1.2 电路...