原书出处
Introduction to Algorithms, Fourth Edition
34 第34章 NP完全性
tonian, since the verification algorithm carefully checks the so-called cycle to be sure.
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
are not the same class. Think of the class P as consisting of problems that can be solved
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea