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


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

  • $\begingroup$ 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. $\endgroup$ – Atinesh Dec 20 '15 at 13:01
  • $\begingroup$ Are you trying to say that - as P ⊆ NP then CO-P ⊆ CO-NP but since P = CO-P this implies P ⊆ CO-NP. $\endgroup$ – Atinesh Dec 20 '15 at 13:05
  • $\begingroup$ Yes, that's what I mean. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.