\text{NP} \cap \text{coNP}: \forall x \in \left\{0,1\right\}^{*}, \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