# Why is P ⊆ co-NP?

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!

## Answers

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!

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.