知识卡片
coNP按补语言属于NP定义
co-NP由补语言定义:语言L属于co-NP,当且仅当L的补语言属于NP。
P对取补封闭,所以P⊆NP∩co-NP;NP是否对取补封闭、NP是否等于co-NP都仍未解决。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
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