\begin{frame}{PSpace-completeness}
  \begin{goal}{}
    \begin{center}
    \includegraphics{pspace.pdf}
    \end{center}
    It is unknown whether these inclusions are strict.
  \end{goal}
  \pause\medskip

  \begin{block}{}
    A language $L \in \text{PSpace}$ is \emph{PSpace-complete}
    if every language $L' \in \text{PSpace}$ is polynomial-time reducible to $L$. 
  \end{block}
  %If we replace \textit{time} by \textit{space}, then PSpace-complete = PSpace \ {\emptyset, \Sigma^*}.

%   \begin{exampleblock}{}
%     Minimizing of NFA's is PSpace-complete.
%   \end{exampleblock}

  \begin{exampleblock}{}
    $L(r) = \Sigma^*\;?$ for regular expression $r$ is PSpace-complete.
  \end{exampleblock}
\end{frame}