# CS254 Lecture 2 – P and NP

Last revised 4/29/2010

In this lecture we define ${{\bf NP}}$, we state the ${{\bf P}}$ versus ${{\bf NP}}$ problem, we prove that its formulation for search problems is equivalent to its formulation for decision problems, and we prove the time hierarchy theorem, which remains essentially the only known theorem which allows to show that certain problems are not in ${{\bf P}}$.