知识卡片
子集和归约的反向证明
若选出的数之和等于目标,每个变量位等于1迫使真假候选恰选一个;每个子句位须等于4,而该位松弛数最多提供3,故至少有一个被选文字数在此位写1。
由此还原出的赋值满足所有子句。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
, k, is satisfied by this assignment. To prove this claim, note that to achieve a sum of 4 in the digit labeled by Cj, the subset S′ must include at least one vi or value that has a 1 in the digit labeled by Cj, since the contributions of the slack variables sj and together sum to at most 3.
参考来源
- 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[115000,120000))。
- 结论依据:第34章原文中的定义、规模界及双向归约证明;涉及图34.17–34.19时已核对图像。
- 原始内容:We claim that every clause C j , for j = 1, 2, … , k , is satisfied by this assignment. To prove this claim, note that to achieve a sum of 4 in the digit labeled by C j , the subset S ′ must include at least one v i or value that has a 1 in the digit labeled by C j , since the contributions of the slack variables s j and together sum to at most 3.