% Preamble
\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage{german}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage[slant]{complexity}
\usepackage{listings}

% Document
\begin{document}

\sffamily

\begin{titlepage}

\thispagestyle{empty}

\begin{center}
\line(1,0){250}
\end{center}

\begin{center}
\Huge \textbf{MATHEMATIQ}
\end{center}

\begin{center}
\line(1,0){250}
\end{center}

\begin{center}
\Large Der Newsletter der MathSIG
\\ \normalsize (Interessensgruppe innerhalb der Mensa \"{O}sterreich)
\end{center}

\begin{center}
\Large Ausgabe 28
\end{center}

\begin{center}
\normalsize \url{http://www.hugi.scene.org/adok/mensa/mathsig/}
\end{center}

\end{titlepage}

\newpage

\begin{center}
\Large \textbf{Editorial}
\end{center}
\normalsize Liebe Leserinnen und Leser!
\\
\\ Dies ist die achtundzwanzigste Ausgabe von MATHEMATIQ, dem Newsletter der MathSIG. Die MathSIG wurde gegr\"{u}ndet, um die spezifischen Interessen mathematisch hochbegabter Menschen zu f\"{o}rdern. In erster Linie soll sie sich also den Themengebieten Mathematik, Informatik, Physik und Philosophie widmen. Beitr\"{a}ge von Lesern sind herzlich willkommen. Wenn in ihnen mathematische Sonderzeichen vorkommen, bitte ich aber, sie zwecks m\"{o}glichst einfacher und fehlerfreier Formatierung im \TeX-Format einzusenden. Als Vorlage ist eine Fassung des jeweils aktuellen Newsletters im \TeX-Format auf Anfrage bei mir erh\"{a}ltlich. Au\ss{}er Artikeln sind nat\"{u}rlich auch Illustrationen f\"{u}r das Titelblatt willkommen. Die Rechte an diesen m\"{u}ssen aber eindeutig bei euch selbst liegen, Kopieren von Bildern aus dem Internet ist nicht erlaubt.
\\
\\ \textbf{Hinweis: Autoren sind f\"{u}r den Inhalt ihrer Artikel oder Werke selbst verantwortlich. Die in MATHEMATIQ ver\"{o}ffentlichten Beitr\"{a}ge widerspiegeln ausschlie\ss{}lich die Meinung ihrer Autoren und nicht jene des Vereins Mensa. Die Zusendung von Beitr\"{a}gen gilt auch als Einverst\"{a}ndnis zu deren Ver\"{o}ffentlichung in MATHEMATIQ.}
\\
\\ \textbf{Diese Ausgabe} besch\"{a}ftigt sich erneut mit dem $\P$-$\NP$-Problem.
\\
\\ In diesem Sinne: Viel Spa\ss{} beim Lesen und Lernen!
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\newpage

\begin{center}
\Large \textbf{Formalisierung des $\P$-$\NP$-Problems}
\end{center}
\normalsize Das $\P$-$\NP$-Problem l\"{a}sst sich durch Pr\"{a}dikatenlogik zweiter Ordnung (second order logic) formalisieren.
\\
\\ $\NP$ bedeutet, dass eine nichtdeterministische Turingmaschine existiert, die f\"{u}r jede L\"{o}sung deren G\"{u}ltigkeit in polynomieller Zeit nachpr\"{u}fen kann. Eine nichtdeterministische Turingmaschine ist im Prinzip eine Sammlung von Algorithmen; wenn das Problem in $\NP$ liegt, gibt es f\"{u}r jede L\"{o}sung mindestens einen Algorithmus, der diese L\"{o}sung in polynomieller Zeit \"{u}berpr\"{u}fen kann. Bei $\P$ gibt es einen Algorithmus, der jede L\"{o}sung in polynomieller Zeit \"{u}berpr\"{u}fen kann. Es gilt also:
\\
\\ $\NP \equiv \forall x \exists A A(x)$
\\ $\P \equiv \exists A \forall x A(x)$
\\
\\ Es l\"{a}sst sich leicht zeigen, dass $\NP(\pi) \to \P(\pi)$, aber nicht $\P(\pi) \to \NP(\pi)$. Ein Beispiel daf\"{u}r ist $\pi \equiv A(x) \wedge B(y) \wedge \neg A(y) \wedge \neg B(x)$.
\\
\\ Auf logischer Ebene kann man also zeigen, dass ein Problem $\pi$, definiert durch eine L\"{o}sungsmenge $\{x, y\}$ und eine Algorithmenmenge $\{A, B\}$, das Pr\"{a}dikat $\NP$ erf\"{u}llen kann, ohne $\P$ zu erf\"{u}llen. Das eigentliche Problem darin besteht zu zeigen, dass diese Eigenschaft auf einen real existierenden Algorithmus zutrifft.
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\end{document}
