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!
Asked
Active
Viewed 1.3k times
13
templatetypedef
- 362,284
- 104
- 897
- 1,065
golmschenk
- 11,736
- 20
- 78
- 137
-
3I personally do not mind this question being asked here, but if others object, you can also ask on http://cs.stackexchange.com – Pascal Cuoq Oct 07 '13 at 23:52
-
This question appears to be off-topic because it is about mathematics – Robert Longson Oct 16 '13 at 12:42
2 Answers
35
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!
templatetypedef
- 362,284
- 104
- 897
- 1,065
3
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.
Omo Odua
- 31
- 1