I know that P is a subset of NP, but I'm not sure what this tells me about P as it relates to coNP? I feel like this is how I should go about proving it, but I'm not sure how. Otherwise, I could find a language that is in both NP and coNP, but I'm not sure how to prove any examples of that.

I know that I can prove L and L complement both exists in P and therefore NP, but I don't know how to relate this to coNP.

  • 3
    $\begingroup$ I think you need to carefully look at the definition of $coNP$ again - your second paragraph suggests you can show that $P \subseteq NP \cap coNP$ (which would be a correct statement). $\endgroup$ Commented Mar 17, 2020 at 1:40
  • $\begingroup$ @LukeMathieson, incorrect here, surely? (I'm not quite sure that that's what the second paragraph says, though.) $\endgroup$
    – LSpice
    Commented Mar 17, 2020 at 3:21
  • $\begingroup$ Please check the title: did you intend P∩coNP =∅? $\endgroup$
    – greybeard
    Commented Mar 17, 2020 at 6:18
  • $\begingroup$ PRIME is both in NP and co-NP. As is COMPOSITE. (Which is taken as an argument that they are both unlikely to be NO-complete) $\endgroup$
    – gnasher729
    Commented Mar 17, 2020 at 7:55

1 Answer 1


Read the definition of NP and co-NP. By that definition, every problem in P is automatically both in NP and co-NP. There’s nothing to prove, that’s how they are defined.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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