知识卡片
松弛数补足子句位
每个子句另配两个仅在该子句位分别为1、2的松弛数。
- 已满足子句由真文字贡献1至3,再选择松弛数补到目标4;
- 未满足子句贡献0,松弛数最多合计3,无法伪造满足。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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