原书出处
Introduction to Algorithms, Fourth Edition
34 第34章 NP完全性
can believe that P ⊆ NP. The famous open question is whether P is a proper subset of NP.
Informally, a problem belongs to the class NPC—and we call it NP-complete—if it belongs to NP and is as “hard” as any problem in NP. We’ll formally define what it means to be as hard as any problem in NP later in this chapter. In the meantime, we state without proof that if any NP-complete problem can be solved in polynomial time, then every problem in NP has a polynomial-time algorithm. Most theoretical computer scientists believe that the NP-complete problems are intractable, since given the wide range of NP-complete problems that have been studied to date—without anyone having discovered a polynomial-time solution to any of them—it would be truly astounding if all of them could be solved in polynomial time. Yet, given the effort devoted thus far to
proving that NP-complete problems are intractable—without a conclusive outcome—we cannot
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea