知识卡片

普通读书笔记卡 · 3713

P类要求多项式时间可解

理解等级:初级

P类包含存在多项式时间算法可求解的判定问题。

这里的n是输入编码长度,指数k须为常数;“多项式”是复杂度分类,不保证高次多项式在实际规模上足够快。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      The class P consists of those problems that are solvable in polynomial time. More specifically, they are problems that can be solved in O(nk) time for some constant k, where n is the size of the input to the problem. Most of the problems examined in previous chapters belong to P. The class NP consists of those problems that are “verifiable” in polynomial time. What do we mean by a problem being verifiable? If you were somehow given a “certificate” of a solution, then

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[0,5000))。 - 结论依据:原文复杂度类别、判定问题、归约或编码定义;不把P与NP的未解关系写成已证明结论。 - 原始内容:The class P consists of those problems that are solvable in polynomial time. More specifically, they are problems that can be solved in O ( n k ) time for some constant k , where n is the size of the input to the problem. Most of the problems examined in previous chapters belong to P. The class NP consists of those problems that are “verifiable” in polynomial time. What do we mean by a problem being verifiable? If you were somehow given a “certificate” of a solution, then