← 返回起始笔记位置

知识卡片

普通读书笔记卡 · 3714.b.8

NP完全归约方向不能倒

理解等级:中级

证明目标问题Y为NP难,应从已知NP完全问题X构造到Y的多项式归约;这样Y的快速解法才会带来X的快速解法。

只完成归约得到NP难,还须证明Y的证书能在多项式时间验证,才能称NP完全。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Make sure that you don’t get the reduction backward. That is, in trying to show that problem Y is NP-complete, you might take a known NP-complete problem X and give a polynomial-time reduction from Y to X. That is the wrong direction. The reduction should be from X to Y, so that a solution to Y gives a solution to X. Remember also that reducing

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[115000,120000))。 - 结论依据:第34章原文中的定义、规模界及双向归约证明;涉及图34.17–34.19时已核对图像。 - 原始内容:Make sure that you don’t get the reduction backward. That is, in trying to show that problem Y is NP-complete, you might take a known NP-complete problem X and give a polynomial-time reduction from Y to X . That is the wrong direction. The reduction should be from X to Y , so that a solution to Y gives a solution to X . Remember also that reducing