知识卡片

普通读书笔记卡 · 3714

NP类允许多项式时间验算证书

理解等级:初级

NP类判定问题的“是”实例有可在输入长度的多项式时间内验证的证书,例如哈密顿环的顶点序列。

能多项式时间求解的问题也能验算,因此P⊆NP;NP不等于“非多项式”。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      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 you could verify that the certificate is correct in time polynomial in the size of the input to the problem. For example, in the hamiltonian-cycle problem, given a directed graph G = (V, E), a certificate would be a sequence 〈v1, v2, v3,

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[0,5000))。 - 结论依据:原文复杂度类别、判定问题、归约或编码定义;不把P与NP的未解关系写成已证明结论。 - 原始内容: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 you could verify that the certificate is correct in time polynomial in the size of the input to the problem. For example, in the hamiltonian-cycle problem, given a directed graph G = ( V , E ), a certificate would be a sequence 〈 v 1 , v 2 , v 3 , …, v | V | 〉 of | V | vertices. You could check in polynomial time that the sequence contains each of the | V | vertices exactly once, that ( v i , v i +1 ) ∈ E for i = 1, 2, 3, …, | V | − 1, and that ( v | V | , v 1 ) ∈ E . As another example, for 3-CNF satisfiability, a certificate could be an assignment of values to variables. You could check in polynomial time that this assignment satisfies the boolean