知识卡片
三合取范式归约保持多项式规模
- 语法树每个连接词最多引入一个变量和局部约束;
- 每个局部约束涉及至多三变量,真值表最多八行;
- 短子句扩充最多四倍。
因此从SAT到3-CNF-SAT的结果长度和构造时间都受多项式界约束。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
We must also show that the reduction can be computed in polynomial time. Constructing ϕ′ from ϕ introduces at most one variable and one clause per connective in ϕ. Constructing ϕ″ from ϕ′ can introduce at most eight clauses into ϕ″ for each clause from ϕ′, since each clause of ϕ′ contains at most three variables, and the truth table for each clause has at most 23 = 8 rows. The construction of ϕ‴ from ϕ″ introduces at most four clauses into ϕ‴ for each clause of ϕ″. Thus the size of the resulting formula ϕ‴ is polynomial in the length of the original formula. Each of the constructions can be accomplished in polynomial time. ▪ Exercises 34.4-1 Consider the
参考来源
- 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[80000,85000))。
- 结论依据:原文§34.4–34.5的3-CNF、团、顶点覆盖和哈密顿环归约;图已核对,跨单元证明留待续读。
- 原始内容:We must also show that the reduction can be computed in polynomial time. Constructing ϕ ′ from ϕ introduces at most one variable and one clause per connective in ϕ . Constructing ϕ ″ from ϕ ′ can introduce at most eight clauses into ϕ ″ for each clause from ϕ ′, since each clause of ϕ ′ contains at most three variables, and the truth table for each clause has at most 2 3 = 8 rows. The construction of ϕ ‴ from ϕ ″ introduces at most four clauses into ϕ ‴ for each clause of ϕ ″. Thus the size of the resulting formula ϕ ‴ is polynomial in the length of the original formula. Each of the constructions can be accomplished in polynomial time. ▪ Exercises 34.4-1 Consider the