\begin{frame}{The Classes EXP and NEXP}
  \begin{block}{}
    A nondeterministic Turing machine $M$ is 
    \begin{itemize}\setlength{\itemsep}{-0.5ex}
      \item \emph{exponential time} if $M$ runs in time $2^{p(|x|)}$ and
      \item \emph{exponential space} if $M$ runs in space $2^{p(|x|)}$
    \end{itemize}
    for some polynomial $p$.
  \end{block}
  \pause

  \begin{goal}{}\vspace{-.5ex}
    \begin{malign}
      \text{\emph{NEXP}} &= \{\, L(M) \mid \text{$M$ nondeterm.\ exponential time TM}\,\} \\[-.5ex]
      \text{\emph{EXP}} &= \{\, L(M) \mid \text{$M$ deterministic exponential time TM}\,\} \\[-.5ex]
      \text{\emph{NEXPSpace}} &= \{\, L(M) \mid \text{$M$ nondeterm.\ exponential space TM}\,\} \\[-.5ex]
      \text{\emph{EXPSpace}} &= \{\, L(M) \mid \text{$M$ deterministic exponential space TM}\,\} 
    \end{malign}
  \end{goal}
  \pause
  
  \begin{block}{}\vspace{-1.5ex}
    \begin{talign}
      \text{P} \,\subseteq\, \text{NP} \,\subseteq\, \text{PSpace} \,\subseteq\, \text{EXP} \,\subseteq\, \text{NEXP} \,\subseteq\, \text{EXPSpace}\\[-3.5ex]
    \end{talign}
    It is unknown whether these inclusions are strict. We know
    \begin{talign}
      \text{P} \neq \text{EXP} && \text{NP} \neq \text{NEXP} && \text{PSpace} \neq \text{EXPSpace} = \text{NEXPSpace}\\[-3ex]
    \end{talign}
  \end{block}

  $\text{PSpace} \subseteq \text{EXP}$ holds since a polynomial-space TM
  can at most take an exponential number of configurations.
\end{frame}