Why is P ⊆ co-NP?

Question

I've seen several places that have simply stated that it's known that P is a subset of the intersection of NP and co-NP. Proofs that show that P is a subset of NP are not hard to find. So to show that it's a subset of the intersection, all that's left to be done is show that P is a subset of co-NP. What might a proof of this be like? Thank you much!

Answer 1

The class P is closed under complementation: if L is a language in P, then the complement of L is also in P. You can see this by taking any polynomial-time decider for L and switching the accept and reject states; this new machine now decides the complement of L and does so in polynomial time.

A language L is in co-NP iff its complement is in NP. So consider any language L ∈ P. The complement of L is also in P, so the complement of L is therefore in NP (because P ⊆ NP). Therefore, L is in co-NP. Consequently, P ⊆ co-NP.

Hope this helps!

Answer 2

Think of it this way. Consider the class co-P. Since P is closed under compliment, P=co-P.

It should also be clear that co-P is a subset of co-NP because P is contained in NP. Since P = co-P, it follows that P is contained in co-NP.