知识卡片

普通读书笔记卡 · 3719.a.3

子集和归约的反向证明

理解等级:高级

若选出的数之和等于目标,每个变量位等于1迫使真假候选恰选一个;每个子句位须等于4,而该位松弛数最多提供3,故至少有一个被选文字数在此位写1。

由此还原出的赋值满足所有子句。

这张卡片看不懂?

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