\documentclass[12pt]{article}
\usepackage{a4,amsmath,amssymb}
\begin{document}
\Large
\begin{center}
\textbf{PSPACE}-Vollst\"andigkeit
\end{center}
\begin{itemize}
\item
\textsc{Quantified Satiasfiability} (QSAT)
\begin{itemize}
\item[$\triangleright$] 
\textit{Instanz}: \\
$X = \{x_1,\overline{x_1}, \ldots,x_n,\overline{x_n}\}$ Literale\\
$C = \{c_1,c_2,\ldots,c_m\}$ Klauseln ($c_i \subseteq X$)\\
$Q = (Q_1,Q_2.\ldots,Q_n) \in \{\forall,\exists\}^n$
Quantorenfolge
\item[$\triangleright$]
\textit{Problem}:\\
Ist 
$Q_1x_1 Q_2 x_2 \ldots Q_n x_n\, 
(\underbrace{c_1 \wedge c_2 \wedge \ldots \wedge c_m}_{
\displaystyle\phi})$ 
= \texttt{true}?
\end{itemize}
\item
Beispiel: $\phi(x_1,x_2,x_3) =$\\ 
$(x_1 \vee x_2 \vee \overline{x}_3) \wedge
(\overline{x}_1 \vee x_2 \vee x_3) \wedge
(\overline{x}_1 \vee \overline{x}_2 \vee \overline{x}_3)$ 
\begin{itemize}
\item
$\forall x_1 \exists x_2 \forall x_3~\phi = \mathtt{false}$
\item
$\forall x_1 \exists x_2 \exists x_3~\phi = \mathtt{true}$
\end{itemize}
\item
\textsc{Theorem}:\\
QSAT ist PSPACE-vollst\"andig unter $\leq_{\mathtt{log-space}}$-Reduktionen
\item
Weitere PSPACE-vollst\"andige Probleme:\\
Spiele auf Graphen wie
\begin{itemize}
\item
\textsc{Generalized Geography}
\item
\textsc{Go}
\item
\textsc{Checkers}
\end{itemize}
\item
Wichtiges Resultat: \textbf{PSPACE} = \textbf{IP}~(\textsc{Shamir} 1992)\\
(IP=Interactive Proofs)
\end{itemize}
\end{document}