知识卡片

普通读书笔记卡 · 3714.e

NP证书长度须有多项式界

理解等级:中级

NP的正式定义要求存在多项式时间验证器,且“是”实例可用长度至多为输入长度多项式的证书得到接受。

验证时间与证书长度两个限制都重要;能多项式时间直接判定的语言可忽略证书,故P⊆NP。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      The complexity class NP The complexity class NP is the class of languages that can be verified by a polynomial-time algorithm.9 More precisely, a language L belongs to NP if and only if there exist a two-input polynomial-time algorithm A and a constant c such that L = {x ∈ {0, 1}*: there exists a certificate y with |y| = O(|x|c) such that A(x, y) = 1}. We say that algorithm A verifies language L in polynomial time. From our earlier discussion about the hamiltonian-cycle problem, you can see that HAM-CYCLE ∈ NP. (It is always nice to know that an important set is nonempty.) Moreover, if L ∈ P, then L ∈ NP, since if there is a polynomial-time algorithm to decide L, the algorithm can be converted to a two-argument verification algorithm that simply ignores any certificate and accepts exactly those input strings it determines to belong to L. Thus, P ⊆ NP. That leaves the question of whether P = NP. A definitive answer is unknown, but most researchers believe that P and NP

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[35000,40000))。 - 结论依据:原文§34.1–34.2的编码、形式语言、验证定义及证明;章末练习不作已解结论。 - 原始内容:The complexity class NP The complexity class NP is the class of languages that can be verified by a polynomial-time algorithm. 9 More precisely, a language L belongs to NP if and only if there exist a two-input polynomial-time algorithm A and a constant c such that L = { x ∈ {0, 1}*: there exists a certificate y with | y | = O (| x | c ) such that A ( x , y ) = 1}. We say that algorithm A verifies language L in polynomial time . From our earlier discussion about the hamiltonian-cycle problem, you can see that HAM-CYCLE ∈ NP. (It is always nice to know that an important set is nonempty.) Moreover, if L ∈ P, then L ∈ NP, since if there is a polynomial-time algorithm to decide L , the algorithm can be converted to a two-argument verification algorithm that simply ignores any certificate and accepts exactly those input strings it determines to belong to L . Thus, P ⊆ NP. That leaves the question of whether P = NP. A definitive answer is unknown, but most researchers believe that P and NP