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
