知识卡片
3CNF归约先给语法树设变量
把原公式解析成一元或二元连接词的树,给每个内部节点输出新设变量;写出节点变量与子表达式等价的局部约束,再与根变量为真合取。
这样保留可满足性,且每个约束只涉及少量变量。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
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.