\begin{frame}{Complexity Classes PSpace and NPSpace}
  \begin{block}{}
    A nondeterministic Turing machine $M$ is \emph{polynomial space}
    if $M$ runs in space $p$ for some polynomial $p$.
  \end{block}
  \pause

  \begin{goal}{}\vspace{-.5ex}
    \begin{malign}
      \text{\emph{NPSpace}} &= \{\, L(M) \mid \text{$M$ nondeterministic polynomial space TM}\,\} \\
      \text{\emph{PSpace}} &= \{\, L(M) \mid \text{$M$ deterministic polynomial space TM}\,\}
    \end{malign}
  \end{goal}
  \pause\medskip
  
  \begin{block}{}
    \begin{malign}
      \text{P} \subseteq \text{PSpace} &&
      \text{NP} \subseteq \text{NPSpace}
    \end{malign}
  \end{block}
  \pause\medskip

  \begin{block}{Theorem of Savitch}
    \begin{malign}
      \text{PSpace} = \text{NPSpace}
    \end{malign}
  \end{block}
  \pause
  Actually, the theorem says something more general: 
  \begin{block}{}
    If $L$ is accepted by a nondeterministic TM in $f(n)$ space,\\
    then $L$ is accepted by a deterministic TM in $f(n)^2$ space.
  \end{block}
\end{frame}