知识卡片
逐门设变量避免共享子式展开
直接递归展开电路为公式,会因高扇出共享子电路被重复复制而可能指数膨胀。
为每条导线设变量、为每个门写等价约束,并要求输出变量为1,可保持公式规模为多项式且与原电路等可满足。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
Unfortunately, this straightforward method does not amount to a polynomial-time reduction. As Exercise 34.4-1 asks you to show, shared subformulas—which arise from gates whose output wires have fan-out of 2 or more—can cause the size of the generated formula to grow exponentially. Thus, the reduction algorithm must be somewhat more clever. Figure 34.10 illustrates how to overcome this problem, using as an example the circuit from Figure 34.8(a). For each wire xi in the circuit C, the formula ϕ has a variable xi. To express how each gate operates, construct a small formula involving the variables of its incident wires. The formula has the form of an “if and only if” (↔), with the variable for the gate’s output on the left and on the right a logical expression encapsulating the gate’s function on its inputs. For example, the operation of the output AND gate (the rightmost gate in the figure) is x10 ↔ (x7 ∧ x8 ∧ x9). We call each of these small formulas a clause. The formula ϕ produced by the reduction algorithm is the AND of the circuit-output variable with the conjunction of clauses