← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

34 第34章 NP完全性

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

beyond the P ≠ NP question remain unresolved. Figure 34.3 shows some possible scenarios.

Despite much work by many researchers, no one even knows whether the class NP is closed under complement. That is, does L ∈ NP imply L ∈ NP? We define the complexity class co-NP as the set of languages L such that L ∈ NP, so that the question of whether NP is closed under complement is also whether NP = co-NP. Since P is closed under complement (Exercise 34.1-6), it follows from Exercise 34.2-9 (P ⊆ co-NP) that P ⊆ NP ∩ co-NP. Once again, however, no one knows whether P = NP ∩ co-NP or whether there is some language in (NP ∩ co-NP) − P. Thus our understanding of the precise relationship between P and NP is woefully incomplete. Nevertheless, even though we might

not be able to prove that a particular problem is intractable, if we can prove that it is

此预览只包含定位所需的摘录和上下文。

原书定位详情

来源:a19c7933-4eda-4176-aebd-30fe7e1ad292

正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml

EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea