知识卡片

普通读书笔记卡 · 3714.b.3.b.1

电路证书可逐门验证

理解等级:高级

给每条导线指定布尔值作为证书,验证器逐门检查输出值是否由输入值正确计算,并检查电路总输出为1。

证书长度及检查时间都受电路规模的多项式界约束,因此CIRCUIT-SAT属于NP。

这张卡片看不懂?

已有反馈 · 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

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[55000,60000))。 - 结论依据:原文§34.2–34.3的复杂度类别、正式归约与电路可满足性;图表或XHTML已核对。 - 原始内容: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