---
title: "NP intersect coNP"
source: https://www.jemoka.com/posts/kbhnp_intersect_conp/
---

\(\text{NP} \cap \text{coNP}: \forall x \in \qty {0,1}^{*}, \exists\) short, efficiently checkable proof of BOTH \(x\) presence/absence in \(L\)
some examples in P: PERFECT-MATCHING in P: PRIMES we don&rsquo;t know if this is in \(P\): FACTORING &hellip; if it was, much of cryptography will break
