…what can we solve efficiently? the “easy” cases by definition all NP/NP Complete problems… SAT 3COL Hamiltonian path problem and also anything in coNP because if \text{P}= \text{NP}, then \text{NP} = \text{coNP} UNSAT NOT-3COL … review: certificates definition of NP, coNP L \in \text{NP} IFF \exists polytime verifier V such that x \in L \Leftrightarrow \exists w \in \left\{0,1\right\}^{\text{poly}\left(|x|\right)}, V\left(x,w\right) = 1 L \in \text{coNP} IFF \exists polytime verifier V such that x \in L \Leftrightarrow \forall w \in \left\{0,1\right\}^{\text{poly}\left(|x|\right)} V\left(x,w\right) = 1 notice how this difference exists only between existential vs universal quantifier (we got here to the expression coNP above by thinking of it as x \not \in L \Leftrightarrow \exists w \left\{0,1\right\}^{\text{poly}\left(|x|\right)} V\left(x,w\right)=1, and the negating this statement)