← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

34 第34章 NP完全性

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.776Z

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