知识卡片

普通读书笔记卡 · 3714.b.3.b.4.a.2.a

3CNF归约先给语法树设变量

理解等级:高级

把原公式解析成一元或二元连接词的树,给每个内部节点输出新设变量;写出节点变量与子表达式等价的局部约束,再与根变量为真合取。

这样保留可满足性,且每个约束只涉及少量变量。

这张卡片看不懂?

已有反馈 · 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.

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[75000,80000))。 - 结论依据:原文§34.3–34.4证明梗概与公式归约;图表或XHTML已核对,不补造省略的形式化细节。 - 原始内容: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 y i 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.