\begin{slide}{Definition, Resultate}

(nach Mojżesz Presburger, 1904--1943)
  \begin{itemize}\itemsep 0pt \parskip 2pt
  \item Prädikatenlogik 
    (d. h. alle Quantoren $\forall, \exists$,
    alle Booleschen Verknüpfungen)
  \item
    Signatur: Fun.-Symbole $0, 1, +$, 
    Rel.-Symbole $=,<, \le$
  \item interpretiert in der Struktur
    der natürlichen Zahlen
  \end{itemize}
Resultate:
\begin{itemize}\itemsep 0pt \parskip 2pt
\item Presburger 1929:
  Allgemeingültigkeit und Erfüllbarkeit 
  solcher Formeln sind entscheidbar
\item Fischer und Rabin 1974:
  Entscheidungsproblem hat Komplexität $\in \Omega(2^{2^n})$
\qquad
  (untere Schranke! selten!)
\end{itemize}

\end{slide}
