知识卡片

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

电路可满足性询问能否输出一

理解等级:中级

CIRCUIT-SAT把仅含与、或、非门的单输出无环组合电路编码为输入,询问是否存在一组布尔输入使输出为1。

若存在称可满足;这不同于问给定一组输入的输出是多少。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第34章 NP完全性 · 查看原书依据

      The circuit-satisfiability problem is, “Given a boolean combinational circuit composed of AND, OR, and NOT gates, is it satisfiable?” In order to pose this question formally, however, we must agree on a standard encoding for circuits. The size of a boolean combinational circuit is the number of boolean combinational elements plus the number of wires in the circuit. We could devise a graph-like encoding that maps any given circuit C into a binary string 〈C〉 whose length is polynomial in the size of the circuit itself. As a formal language, we can therefore define CIRCUIT-SAT = {〈C〉 : C is a satisfiable boolean combinational circuit}. The circuit-satisfiability problem arises in the area of computer-aided hardware optimization. If a subcircuit always produces 0, that

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[55000,60000))。 - 结论依据:原文§34.2–34.3的复杂度类别、正式归约与电路可满足性;图表或XHTML已核对。 - 原始内容:The circuit-satisfiability problem is, “Given a boolean combinational circuit composed of AND, OR, and NOT gates, is it satisfiable?” In order to pose this question formally, however, we must agree on a standard encoding for circuits. The size of a boolean combinational circuit is the number of boolean combinational elements plus the number of wires in the circuit. We could devise a graph-like encoding that maps any given circuit C into a binary string 〈 C 〉 whose length is polynomial in the size of the circuit itself. As a formal language, we can therefore define CIRCUIT-SAT = { 〈 C 〉 : C is a satisfiable boolean combinational circuit}. The circuit-satisfiability problem arises in the area of computer-aided hardware optimization. If a subcircuit always produces 0, that