知识卡片
NP证书长度须有多项式界
NP的正式定义要求存在多项式时间验证器,且“是”实例可用长度至多为输入长度多项式的证书得到接受。
验证时间与证书长度两个限制都重要;能多项式时间直接判定的语言可忽略证书,故P⊆NP。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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