知识卡片

普通读书笔记卡 · 3714.f

coNP按补语言属于NP定义

理解等级:中级

co-NP由补语言定义:语言L属于co-NP,当且仅当L的补语言属于NP。

P对取补封闭,所以P⊆NP∩co-NP;NP是否对取补封闭、NP是否等于co-NP都仍未解决。

这张卡片看不懂?

已有反馈 · 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

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[40000,45000))。 - 结论依据:原文§34.2–34.3的复杂度类别、正式归约与电路可满足性;图表或XHTML已核对。 - 原始内容: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