知识卡片
电路证书可逐门验证
给每条导线指定布尔值作为证书,验证器逐门检查输出值是否由输入值正确计算,并检查电路总输出为1。
证书长度及检查时间都受电路规模的多项式界约束,因此CIRCUIT-SAT属于NP。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
Lemma 34.5 The circuit-satisfiability problem belongs to the class NP. Proof We provide a two-input, polynomial-time algorithm A that can verify CIRCUIT-SAT. One of the inputs to A is (a standard encoding of) a boolean combinational circuit C. The other input is a certificate corresponding to an assignment of a boolean value to each of the wires in C. (See Exercise 34.3-4 for a smaller certificate.) The algorithm A works as follows. For each logic gate in the circuit, it checks that the value provided by the certificate on the output wire is correctly computed as a function of the values on the input wires. Then, if the output of the entire circuit is 1, algorithm A outputs 1, since the values assigned to the inputs of C provide a satisfying assignment. Otherwise, A outputs 0. Whenever a satisfiable circuit C is input to algorithm A, there exists a