我看到过一些地方简单地陈述了P是NP和co-NP的交集的子集这一事实。显示P是NP的子集的证明并不难找到。因此，为了展示它是交集的子集，唯一剩下要做的就是展示P是co-NP的子集。那么，这种证明可能是什么样子的呢？非常感谢！
为什么 P ⊆ co-NP？
13
- golmschenk
2
4我个人不介意在这里被问到这个问题，但如果其他人反对，你也可以在http://cs.stackexchange.com上提出。 - Pascal Cuoq
这个问题似乎不适合讨论，因为它涉及到数学。 - Robert Longson
2个回答
35
如果L是P类语言，则L的补集也是P类语言。这可以通过取L的任何多项式时间决策器并切换接受和拒绝状态来实现；这台新机器现在在多项式时间内决定L的补集。
如果一个语言L在NP中，那么它的补集也在NP中。因此考虑任意语言L属于P类语言，L的补集也属于P类语言，所以L的补集也在NP中（因为P ⊆ NP）。因此，L属于co-NP。因此，P ⊆ co-NP。
希望这能帮到您！
- templatetypedef
1
明确的回答，我很喜欢！ - alan23273850
3
从这个角度来看。考虑类co-P。由于P在补集下是封闭的，所以P = co-P。
很明显，co-P是co-NP的子集，因为P包含在NP中。因为P = co-P，所以P包含在co-NP中。
- Omo Odua
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接