\(\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’t know if this is in \(P\): FACTORING … if it was, much of cryptography will break