原书出处
Introduction to Algorithms, Fourth Edition
34 第34章 NP完全性
n algorithm has a variable for each wire in the circuit and a clause for each logic gate.
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
describing the operation of each gate. For the circuit in the figure, the formula is ϕ =
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea