\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}