0
$\begingroup$

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.

$\endgroup$
4
  • 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$ Mar 17 '20 at 1:40
  • $\begingroup$ @LukeMathieson, incorrect here, surely? (I'm not quite sure that that's what the second paragraph says, though.) $\endgroup$
    – LSpice
    Mar 17 '20 at 3:21
  • $\begingroup$ Please check the title: did you intend P∩coNP =∅? $\endgroup$
    – greybeard
    Mar 17 '20 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
    Mar 17 '20 at 7:55
2
$\begingroup$

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.

$\endgroup$

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.