为什么P⊆co-NP？

Question

我已经看过几个地方简单地说已知P是NP和co-NP的交集的子集.证明P是NP子集的证据并不难找到.因此,为了表明它是交集的一个子集,剩下要做的就是表明P是co-NP的子集.什么可以证明这一点？非常感谢!

Answer 1

P类在互补下闭合:如果L是P中的语言,则L的补码也在P中.您可以通过对L采用任何多项式时间决策器并切换接受和拒绝状态来看到这一点; 这个新机器现在决定L的补码,并在多项式时间内完成.

语言L在共同NP中,如果其补语在NP中.因此,考虑任何语言L∈ P.L的补体也是P,因此,因此L的补体是在NP(因为P ⊆ NP).因此,L在共同NP中.因此,P ⊆共NP.

希望这可以帮助!