← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

34 第34章 NP完全性

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.781Z

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