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 PNP). 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.


Need Your Help

How to rebase one Git repository onto another one?

git merge repository rebase

I had one Git repository (A) which contains the development of a project until a certain point. Then I lost the USB stick this repo A was on. Luckily I had a backup of the latest commit, so I could

Converting an UnsafePointer with length to a Swift Array type

c arrays swift unsafe-pointers

I'm looking for the simplest ways to achieve reasonable C interoperability in Swift, and my current block is converting an UnsafePointer<Int8> (which was a const char *), into an [Int8] array.