原书出处
Introduction to Algorithms, Fourth Edition
34 第34章 NP完全性
m. The first step is similar to the one used to prove CIRCUIT-SAT ≤P SAT in Theorem 34.9.
First, construct a binary “parse” tree for the input formula ϕ, with literals as leaves and connectives as internal nodes. Figure 34.11 shows such a parse tree for the formula If the input formula contains a clause such as the OR of several literals, use associativity to parenthesize the expression fully so that every internal node in the resulting tree has just one or two children. The binary parse tree is like a circuit for computing the function. Mimicking the reduction in the proof of Theorem 34.9, introduce a variable yi for the output of each internal node. Then rewrite the original formula ϕ as the AND of the variable at the root of the parse tree and a conjunction of clauses describing the operation of each node.
For the formula (34.3), the resulting expression is ϕ′ = y1 ∧ (y1 ↔ (y2 ∧ ¬x2)) ∧ (y2 ↔ (
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea