\begin{frame}{Complexity Classes P and NP} \begin{block}{} A nondeterministic Turing machine $M$ is \emph{polynomial time} if $M$ runs in time $p$ for some polynomial $p$. \end{block} Equivalently, $M$ has time complexity $O(n^k)$ for some $k$. \pause\medskip \begin{goal}{} \emph{NP} is the class of languages accepted by \alert{nondeterministic} polynomial time Turing machines: \begin{talign} \text{\emph{NP}} = \{\, L(M) \mid \text{$M$ is nondeterministic polynomial time TM}\,\} \end{talign} \end{goal} \pause \begin{goal}{} \emph{P} is the class of languages accepted by \alert{deterministic} polynomial time Turing machines: \begin{talign} \text{\emph{P}} = \{\, L(M) \mid \text{$M$ is deterministic polynomial time TM}\,\} \end{talign} \end{goal} \pause\medskip \begin{alertblock}{} Clearly $\text{P} \subseteq \text{NP}$, but it is unknown whether $\text{P} = \text{NP}$. \end{alertblock} \end{frame}