知识卡片
电路可满足性询问能否输出一
CIRCUIT-SAT把仅含与、或、非门的单输出无环组合电路编码为输入,询问是否存在一组布尔输入使输出为1。
若存在称可满足;这不同于问给定一组输入的输出是多少。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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