← 返回起始笔记位置

知识卡片

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

无进位保证按位推理

理解等级:中级

归约中任一子句位最多收到三个文字数的1,再加两个松弛数的1与2,合计最多6;用十进制编码便不会进位。

这样整数和等于目标才可逐位解释为变量选择与子句满足,不能忽略进位条件。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      The greatest sum of digits in any one digit position is 6, which occurs in the digits labeled by clauses (three 1s from the vi and values, plus 1 and 2 from the sj and values). Interpreting these numbers in base 10, therefore, no carries can occur from lower digits to higher digits.12 The reduction can be performed in polynomial time. The set S

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[110000,115000))。 - 结论依据:第34章原文中的定义、规模界及双向归约证明;涉及图34.17–34.19时已核对图像。 - 原始内容:The greatest sum of digits in any one digit position is 6, which occurs in the digits labeled by clauses (three 1s from the v i and values, plus 1 and 2 from the s j and values). Interpreting these numbers in base 10, therefore, no carries can occur from lower digits to higher digits. 12 The reduction can be performed in polynomial time. The set S