# How to prove P ⊆ Co-NP

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

## 2 Answers

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

• I don't understand this line " since P ⊆ NP we have that the complement of this problem is in Co-NP". Can you please elaborate it. – Atinesh Dec 20 '15 at 13:01
• Are you trying to say that - as P ⊆ NP then CO-P ⊆ CO-NP but since P = CO-P this implies P ⊆ CO-NP. – Atinesh Dec 20 '15 at 13:05
• Yes, that's what I mean. – Albert Hendriks Dec 20 '15 at 16:52

A deterministic polynomial time machine for a language $L$ can easily be converted to a non-deterministic polynomial time machine which has the same operational semantics (that is, it operates deterministically), and so it both non-deterministically and co-non-deterministically accept $L$ – just check the definitions.