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

% 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 3
\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 dritte 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{Diese Ausgabe} ist wieder den formalen Sprachen gewidmet. Dazu passend habe ich als Einf\"{u}hrung in die Komplexit\"{a}tstheorie auch meinen Artikel \"{u}ber das $\P$-$\NP$-Problem \"{u}bernommen, der einigen Lesern bereits aus TOPIQ 365 bekannt sein d\"{u}rfte. Die hier wiedergegebene Fassung ist leicht \"{u}berarbeitet und mathematisch pr\"{a}ziser formuliert. Ich werde in Zukunft meine schon in TOPIQ ver\"{o}ffentlichten themenrelevanten Artikel nochmals bringen, um die durch MATHEMATIQ dargestellte Sammlung zu vervollst\"{a}ndigen.
\\
\\ 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{Formale Sprachen, Teil 2}
\end{center}
\normalsize Auch kontextfreie Sprachen k\"{o}nnen durch Automaten definiert werden. Man verwendet dazu so genannte Pushdown-Automaten. Diese arbeiten mit einem Stack, zu deutsch Stapelspeicher. Das ist in der Informatik eine relativ weit verbreitete Datenstruktur, die im Wesentlichen eben so funktioniert, wie ihr Name es sagt. Wenn man beispielsweise einen Stapel von B\"{u}chern anlegt, dann kann man immer ein weiteres Buch auf den Stapel legen, aber wenn man ein bestimmtes Buch haben will, muss man beim jeweils obersten Buch anfangen, die B\"{u}cher schrittweise abzutragen. Anders gesagt: Ein Stapel ist ein LIFO-Speicher (\textit{last in, first out}). Ein Pushdown-Automat macht sich nun einen Stapel als zus\"{a}tzliches Kriterium zunutze, ob ein bestimmter Zustands\"{u}bergang erlaubt ist: Bei jedem \"{U}bergang ist es m\"{o}glich, das oberste Speicherelement aus dem Stapel zu holen und festzulegen, dass der \"{U}bergang nur zul\"{a}ssig ist, wenn dieses Speicherelement einen bestimmten Wert hat. Au\ss{}erdem darf bei jedem \"{U}bergang ein neuer Wert auf den Stapel gelegt werden. Mit einem solchen Automaten l\"{a}sst sich entscheiden, ob ein gegebenes Wort Element der kontextfreien Sprache ist, welche dieser Automat repr\"{a}sentiert.
\\
\\ Dass ein solcher Automat in der Lage ist, eine kontextfreie Sprache abzubilden, l\"{a}sst sich leicht zeigen: Wenn auf der rechten Seite einer Regel nur Literale stehen, wird der Stack nicht ben\"{o}tigt. Wenn rechts auch Verweise auf andere Regeln vorkommen, dann kann der Stack genutzt werden, um, sobald ein solcher Verweis erreicht wurde, abzuspeichern, an welcher Stelle der Automat nach dem Abarbeiten dieser Regel weitermachen soll. Kommt beispielsweise innerhalb der Regel A ein Verweis auf die Regel B vor, arbeitet der Automat das Eingabewort solange nach der Regel A ab, bis dieser Verweis erreicht wird. Dann speichert er auf dem Stack, wo er weitermachen muss, sobald die Abarbeitung der Regel B fertig ist, und arbeitet das Eingabewort nach der Regel B ab. Sobald die Abarbeitung nach der Regel B erledigt ist, sieht der Automat durch Zugriff auf den Stack nach, wo er fortsetzen muss. Nach der Abarbeitung der Regel A erkennt er dann, dass der Stack leer ist, und akzeptiert das Eingabewort.
\\
\\ Fehlt nur der Beweis, dass ein solcher Pushdown-Automat nur kontextfreie und nicht auch in der Chomsky-Hierarchie niedriger stehende Sprachen abarbeiten kann. Nat\"{u}rlich l\"{a}sst sich zeigen, dass ein Pushdown-Automat nicht in der Lage ist, kontextsensitive Sprachen abzuarbeiten, die nicht zugleich kontextfreie Sprachen sind. Kontextsensitive Sprachen k\"{o}nnen durch Grammatiken definiert werden, in denen Regeln wie bei kontextfreien Sprachen vorkommen, zudem aber auch Regeln, in denen auch auf der linken Seite Literale vorkommen. Also Regeln wie etwa
\\
\\ \textit{a A b $\to$ b C d}.
\\
\\ Den Beweis \"{u}berlasse ich den Lesern als \"{U}bungsaufgabe. Ein Tipp: Es hat damit zu tun, dass Automaten das Eingabewort sequenziell verarbeiten, also ein Literal nach dem anderen in exakt der Reihenfolge, in der diese Literale im Eingabewort vorkommen. Wieso kann das bei kontextsensitiven Sprachen ein Problem sein? W\"{a}re es theoretisch m\"{o}glich, mit Pushdown-Automaten auch zu Literalen, die bereits abgearbeitet worden sind, zur\"{u}ckzuspringen? Wieso reicht das nicht aus, um kontextsensitive Sprachen durch Pushdown-Automaten zu definieren?
\\
\\ Eine M\"{o}glichkeit, zu bereits abgearbeiteten Literalen zur\"{u}ckzuspringen und dennoch die zus\"{a}tzlich ben\"{o}tigten (Zustands-)Informationen abzuspeichern, die man beim Verarbeiten von kontextsensitiven Sprachen braucht, ist die Verwendung von Turing-Maschinen. Eine Turing-Maschine ist deutlich m\"{a}chtiger als ein Automat. Sie kann verschiedene Zust\"{a}nde haben, die Eingabedaten sowohl von links nach rechts als auch in umgekehrter Richtung einlesen sowie die Eingabedaten \"{u}berschreiben. Konkret wird eine Turing-Maschine genauso wie ein Automat durch verschiedene Zust\"{a}nde und deren \"{U}berg\"{a}nge repr\"{a}sentiert. Genau ein Zustand ist der Ausgangszustand und mindestens ein Zustand Endzustand. Das Eingabewort wird angenommen, wenn ein Endzustand erreicht wird. Welche \"{U}berg\"{a}nge m\"{o}glich sind, h\"{a}ngt einerseits vom aktuellen Zustand ab, andererseits aber auch von dem Literal, das sich an der aktuellen Stelle des Schreib-/Lesekopfs befindet. Jeder \"{U}bergang bestimmt nicht nur den Folgezustand, sondern auch, mit welchem Wert das aktuelle Eingabedatum \"{u}berschrieben werden und in welche Richtung sich der Schreib-/Lesekopf bewegen sollte.
\\
\\ Durch Turingmaschinen lassen sich nicht nur kontextsensitive Sprachen beschreiben, sondern allgemeinere Mengen von Sprachen. Wenn man festlegt, dass die Turingmaschine das Eingabewort in jedem Fall entweder akzeptieren oder zur\"{u}ckweisen muss, aber nicht in einer Endlosschleife h\"{a}ngenbleiben darf, nennt man diese Turingmaschine auch Turing-Entscheider. Durch Turing-Entscheider repr\"{a}sentierte Sprachen hei\ss{}en rekursive Sprachen. Gestattet man, dass die Turingmaschine in einer Endlosschleife h\"{a}ngenbleiben darf, wenn ein Wort nicht zu der durch sie beschriebenen Sprache geh\"{o}rt, aber andernfalls das Wort akzeptieren muss, nennt man die auf diese Weise definierbare Menge von Sprachen rekursiv aufz\"{a}hlbar. Es gibt auch die Menge der co-rekursiv aufz\"{a}hlbaren Sprachen: Diese entsprechen Turingmaschinen, die ein Wort in jedem Fall zur\"{u}ckweisen, wenn es nicht in der Sprache enthalten ist, und die andernfalls entweder das Wort akzeptieren oder in einer Endlosschleife h\"{a}ngenbleiben m\"{u}ssen. Logischerweise stellt die Menge der rekursiven Sprachen die Schnittmenge der Menge der rekursiv aufz\"{a}hlbaren Sprachen und der Menge der co-rekursiv aufz\"{a}hlbaren Sprachen dar. Rekursiv aufz\"{a}hlbaren Sprachen entsprechende Entscheidungsprobleme werden \"{u}brigens auch semi-entscheidbar genannt.
\\
\\ Damit h\"{a}tte ich die wichtigsten Mengen von formalen Sprachen genannt und definiert. In einem m\"{o}glichen dritten Teil dieser Serie k\"{o}nnte ich noch die Pumping-Lemmata vorstellen, mit denen man beweisen kann, dass eine gegebene Sprache nicht kontextfrei oder zumindest nicht regul\"{a}r ist.
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\newpage

\begin{center}
\Large \textbf{Errata}
\end{center}
\normalsize Der erste Teil des Artikels zu den formalen Sprachen aus MATHEMATIQ Ausgabe 2 enthielt einige kleinere Schnitzer. Erstens ist es nicht ganz korrekt, von Klassen von Sprachen zu sprechen, weil Klassen ja im strengen Wortsinn disjunkte Mengen sind, die meisten der in der Chomsky-Hierarchie vorkommenden Mengen von Sprachen aber Teilmengen von anderen in der Hierarchie vorkommenden Sprachen sind. Also darf man eigentlich nur von Mengen und nicht von Klassen sprechen, wenn man ganz korrekt sein will. Weiters habe ich mindestens einmal von der in der Hierarchie ``n\"{a}chsth\"{o}heren'' Sprache gesprochen, dabei handelte es sich aber um die n\"{a}chsttiefere Sprache, weil ja die h\"{o}heren Hierarchiebenen Teilmengen der niedrigeren Hierarchieebenen sind und nicht umgekehrt. Das ist mir jedenfalls jetzt beim nochmaligen Lesen des Artikels aufgefallen. Aber es handelt sich nat\"{u}rlich nur um Kleinigkeiten, und im Wesentlichen sollte der Artikel stimmen.
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\newpage

\begin{center}
\Large \textbf{Das $\P$-$\NP$-Problem}
\end{center}
\normalsize Dies ist eines der schwierigsten noch ungel\"{o}sten Probleme der Informatik. Es z\"{a}hlt zu den Millennium-Prize-Problemen, und die erste Person, die eine L\"{o}sung publiziert, wird vom Clay Mathematics Institute 1 Million Dollar bekommen.
\\
\\ $\P$ und $\NP$ sind Mengen von Entscheidungsproblemen, die eine bestimmte Komplexit\"{a}t haben. Umgangssprachlich nennt man $\P$ und $\NP$, wenn auch nicht ganz korrekt, deswegen auch Komplexit\"{a}tsklassen. Dies bedeutet, dass es einen Algorithmus gibt, der das jeweilige Entscheidungsproblem l\"{o}st und dessen Laufzeit selbst im schlechtesten Fall ein gegebenes Limit nicht \"{u}berschreiten wird. Egal mit welchen Eingabedaten man den Algorithmus ausf\"{u}hrt, ben\"{o}tigt der Algorithmus, wenn das zu ihm geh\"{o}rende Entscheidungsproblem in die Klasse $\P$ f\"{a}llt, nur eine polynomielle Anzahl von Schritten in Bezug auf die Gr\"{o}\ss{}e der Eingabedaten (also eine Konstante multipliziert mit der Gr\"{o}\ss{}e der Eingabedaten hoch eine andere Konstante), um die Ausgabedaten zu berechnen. Im Gegensatz dazu bedeutet $\NP$, dass es m\"{o}glich ist, eine Kandidatenl\"{o}sung in einer polynomiellen Zeit in Bezug auf die Gr\"{o}\ss{}e der L\"{o}sung auf Korrektheit zu \"{u}berpr\"{u}fen.
\\
\\ Jeder Algorithmus, der in $\P$ ist, ist auch in $\NP$. Hat man die L\"{o}sung f\"{u}r ein gegebenes Problem in $\P$, kann man diese L\"{o}sung auch in einer polynomiellen Anzahl von Schritten verifizieren. Die Frage ist, ob es auch andersrum m\"{o}glich sei. Die meisten Informatiker denken, nein. Sollte sich aber herausstellen, dass jedes Problem in $\NP$ auch in $\P$ ist, w\"{a}re das eine wahre Revolution, weil sie die Berechnung vieler Probleme deutlich beschleunigen w\"{u}rde.
\\
\\ Um zu beweisen, dass $\P$ und $\NP$ gleich sind, w\"{u}rde es reichen, es f\"{u}r ein einziges $\NP$-vollst\"{a}ndiges Problem zu beweisen. $\NP$-vollst\"{a}ndige Probleme stellen eine Teilmenge von $\NP$ dar, mit der Eigenschaft, dass sie zumindest so schwierig wie jedes andere Problem in NP sind. Ein Problem, f\"{u}r das diese Eigenschaft bewiesen wurde, ist das Erf\"{u}llbarkeitsproblem der Aussagenlogik (SAT, Satz von Cook und Levin). Um f\"{u}r ein anderes Problem zu zeigen, dass dieses ebenfalls $\NP$-vollst\"{a}ndig ist, reicht es aus zu beweisen, dass es in $\NP$ ist, und dass es zumindest so schwierig wie SAT ist. Letzteres kann erreicht werden, indem man einen Weg findet, SAT zu diesem Problem zu reduzieren, also einen Weg zu finden, wie ein Algorithmus f\"{u}r dieses neue Problem Instanzen von SAT l\"{o}sen k\"{o}nnte. Bis jetzt wurde noch kein einziger polynomieller Algorithmus f\"{u}r ein $\NP$-vollst\"{a}ndiges Problem gefunden.
\\
\\ Es scheint realistischer zu sein, einen Beweis daf\"{u}r zu finden, dass $\P$ ungleich $\NP$ ist, aber auch diese Suche gestaltet sich sehr schwierig. Eine M\"{o}glichkeit w\"{a}re es zu zeigen, dass es f\"{u}r ein bestimmtes $\NP$-vollst\"{a}ndiges Problem gar keinen Algorithmus mit polynomieller Laufzeit geben kann, aber wie sollte man dies bewerkstelligen? Zu beweisen, dass etwas nicht m\"{o}glich ist, scheint viel schwieriger zu sein als das Gegenteil zu beweisen, und aus diesem Grund wird das $\P$-$\NP$-Problem immer noch als ungel\"{o}st betrachtet.
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\newpage

\begin{center}
\Large \textbf{Ressourcen}
\end{center}
\normalsize Beim Surfen im Internet sind mir einige Links untergekommen, die f\"{u}r Mathematikinteressierte wertvoll sein k\"{o}nnten.
\begin{itemize}
\normalsize \item The 12 Most Controversial Facts In Mathematics
\\ \small \url{http://www.businessinsider.com/the-most-controversial-}
\\ \small \url{math-problems-2013-3}
\normalsize \item 9 More Super-Controversial Math Facts
\\ \small \url{http://www.businessinsider.com/controversial-math-problems-}
\\ \small \url{markov-chain-cantor-coin-flip-2013-5}
\normalsize \item Beal-Vermutung (Preisgeld von 1 Million Dollar!)
\\ \small \url{http://www.spiegel.de/wissenschaft/mensch/}
\\ \small \url{andrew-beal-lobt-eine-million-fuer-loesen-}
\\ \small \url{der-beal-vermutung-aus-a-904122.html}
\end{itemize}
Ich habe mir heute auch ein neues Buch zugelegt. Es hei\ss{}t ``After G\"{o}del: Platonism and Rationalism in Mathematics and Logic''. Der Autor ist Richard Tieszen, Professor der Philosophie an der San Jos\'e State University in California. Das Ziel des Buchs ist es, ``eine vertretbare Position zum platonischen Rationalismus in Mathematik und Logik zu finden''. Sobald ich mit dem Lesen fertig sein werde, werde ich wohl den Inhalt dieses Buchs in MATHEMATIQ zusammenfassen.
\begin{flushright}
\normalsize Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\end{document}
