-3
$\begingroup$

We currently don't know the relationship between NP and co-NP, but would it be possible to show whether the intersection is equal to P? I can't think of any languages in both NP and co-NP, but not in P.

$\endgroup$
1
  • $\begingroup$ Note that you can't prove that any NP problem is outside of P as that would imply that P != NP $\endgroup$ Feb 13 '19 at 13:13
3
$\begingroup$

Proving that $P= NP \cap$ co-$NP$ is an open problem and believed to be unlikely since Integer factoring decision problem is in both $NP$ and co-$NP$ but conjectured to be outside $P$.

$\endgroup$

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