[Solved]: How to prove P ⊆ Co-NP

Problem Detail: 

My approach

Let L ∈ P

$\exists$ Turing Machine $M_1$ which decides L.

We can easily construct $M_2$ which decides $\bar{L}$

$\bar{L}$ ∈ CO-NP $\implies$ P ⊆ Co-NP

I'm not sure whether its a correct way to prove this or not. I found this method here Link

Asked By : Atinesh

Answered By : Albert Hendriks

It's because P = Co-P: if we can find a solution for a problem in Polynomial time, we can also decide in Polynomial time that it does NOT have a solution. Now, since P ⊆ NP we have that the complement of this problem is in Co-NP. But the complement of any problem in P is in Co-P and therefore any complement of any P problem is in Co-NP. And since the complement of any P problem is Co-P = P, we have P ⊆ Co-NP

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50931

 Ask a Question

 Download Related Notes/Documents