知识卡片

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

松弛数补足子句位

理解等级:高级

每个子句另配两个仅在该子句位分别为1、2的松弛数。

  • 已满足子句由真文字贡献1至3,再选择松弛数补到目标4;
  • 未满足子句贡献0,松弛数最多合计3,无法伪造满足。
这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第34章 NP完全性 · 查看原书依据

      For each clause Cj, set S contains two integers sj and . Each of sj and has 0s in all digits other than the one labeled by Cj. For sj, there is a 1 in the Cj digit, and has a 2 in this digit. These integers are “slack variables,” which we use to get each clause-labeled digit position to add to the target value of 4. Simple inspection of

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[110000,115000))。 - 结论依据:第34章原文中的定义、规模界及双向归约证明;涉及图34.17–34.19时已核对图像。 - 原始内容:For each clause C j , set S contains two integers s j and . Each of s j and has 0s in all digits other than the one labeled by C j . For s j , there is a 1 in the C j digit, and has a 2 in this digit. These integers are “slack variables,” which we use to get each clause-labeled digit position to add to the target value of 4. Simple inspection of