% 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 11
\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 elfte 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} setzt den Themenschwerpunkt ``Theoretische Informatik'' fort.
\\
\\ 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{Das Erf\"{u}llbarkeitsproblem der Aussagenlogik}
\end{center}
\normalsize Ein $\NP$-vollst\"{a}ndiges Problem ist das Erf\"{u}llbarkeitsproblem der Aussagenlogik, auch \textit{Satisfiability} oder kurz \textit{SAT} genannt. Dabei geht es darum, eine Belegung der Variablen einer gegebenen aussagenlogischen Formel zu finden, die beweist, dass diese Formel erf\"{u}llbar ist. Sollte es eine solche Belegung nicht geben, soll das Programm ausgeben, dass die Formel nicht erf\"{u}llbar ist. Das Problem bei der Sache ist, dass es unter Umst\"{a}nden zwar gen\"{u}gt, eine einzige Belegung zu \"{u}berpr\"{u}fen, um zur Konklusion zu kommen, dass die Formel erf\"{u}llbar ist. Aber um das Gegenteil zu beweisen, muss man alle m\"{o}glichen Belegungen probieren - und das sind $2^n$, also eine exponentielle Zahl (wobei $n$ f\"{u}r die Anzahl der Variablen steht). Deswegen ist \textit{SAT} in $\NP$, aber wahrscheinlich nicht in $\P$. 
\\
\\ Sollte es aber einen Algorithmus mit polynomieller Laufzeit in Bezug auf die Anzahl der Variablen geben, der in der Lage ist, \textit{SAT} zu l\"{o}sen, dann liegt \textit{SAT} und damit auch jedes andere Problem, das in der Menge $\NP$ enthalten ist, auch in $\P$ - damit w\"{a}re das $\P$-$\NP$-Problem in Sinne von $\P = \NP$ gel\"{o}st. Das ist jedoch eher unwahrscheinlich, weil gemeinhin angenommen wird, dass $\P \neq \NP$ gilt. Denn das Gegenteil w\"{a}re so leicht zu beweisen (es w\"{u}rde gen\"{u}gen, einen einzigen polynomiellen Algorithmus f\"{u}r ein beliebiges $\NP$-vollst\"{a}ndiges Problem zu finden), dass die Tatsache, dass dies im Laufe all der Jahrzehnte, in denen sich Forscher mit diesem Problem schon besch\"{a}ftigt haben, noch niemanden gelungen ist, es sehr unwahrscheinlich erscheinen l\"{a}sst, dass es zutreffen k\"{o}nnte.
\\
\\ Wie k\"{o}nnte man mit Hilfe von \textit{SAT} aber $\P \neq \NP$ beweisen? Hierzu folgender Gedankengang: Die Gr\"{o}\ss{}e des L\"{o}sungsraums betr\"{a}gt bekanntlich $2^n$. Entscheidend ist aber nicht die Gr\"{o}\ss{}e des L\"{o}sungsraums, sondern die Gr\"{o}\ss{}e des Suchraums. Gibt es einen Algorithmus, der, auch wenn der L\"{o}sungsraum exponentiell ist, nur eine polynomielle Anzahl von L\"{o}sungsm\"{o}glichkeiten durchsuchen muss? Wenn ja, dann ist $\P = \NP$; wenn nein, dann ist $\P \neq \NP$.
\\
\\ Dass der Suchraum grunds\"{a}tzlich polynomiell oder sogar noch kleiner sein kann, auch wenn der L\"{o}sungsraum exponentiell ist, zeigt das Problem \textit{2-COL}, also ob man einen Graphen mit nur zwei Farben f\"{a}rben kann, so dass es kein Paar miteinander durch eine Kante verbundener Knoten gibt, die die gleiche Farbe zugewiesen bekommen. Hier kann jedem Knoten eine von zwei verschiedenen Farben zugewiesen werden, der L\"{o}sungsraum hat daher wieder die Gr\"{o}\ss{}e $2^n$. Aber de facto muss nur eine einzige L\"{o}sung betrachtet werden, der Suchraum hat also die Gr\"{o}\ss{}e 1, ist ergo konstant. Denn es gen\"{u}gt, bei einem beliebigen Knoten zu beginnen und dann jeweils die Nachbarknoten anzuf\"{a}rben; jeder Knoten muss h\"{o}chstens einmal gef\"{a}rbt werden, und zur Ermittlung seiner Farbe muss nur jeder seiner Nachbarknoten einmal betrachtet werden, womit sich eine Obergrenze von $n^2$ ergibt. K\"{o}nnen auf diese Weise alle Knoten gef\"{a}rbt werden, so ist der Graph mit zwei Farben f\"{a}rbbar; entsteht hingegen die Situation, dass einem Knoten keine der beiden Farben zugewiesen werden kann, weil er bereits mit Knoten beider Farben benachbart ist, so ist bewiesen, dass der Graph nicht mit zwei Farben f\"{a}rbbar ist.
\\
\\ Theoretisch ist es also sehr wohl m\"{o}glich, dass ein Problem, das einen exponentiellen L\"{o}sungsraum hat, in polynomieller Zeit gel\"{o}st werden kann. Die Frage ist nur, ob das auch f\"{u}r \textit{SAT} gilt - und vor allem: wie man beweisen sollte, dass es f\"{u}r \textit{SAT} \textbf{nicht} gilt, wie es wahrscheinlich der Fall ist? Zu beweisen, dass etwas nicht gilt, ist unendlich viel schwieriger, als das Gegenteil zu beweisen!
\\
\\ Als \textbf{\"{U}bungsaufgabe} \"{u}berlasse ich euch zu beweisen, dass \textit{2-COL} nicht $\NP$-vollst\"{a}ndig ist, also man \textit{SAT} nicht auf \textit{2-COL} reduzieren kann (sehr wohl aber umgekehrt!).
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\newpage

\begin{center}
\Large \textbf{Zum Beweis der Nichtexistenz}
\end{center}
\normalsize Wie ich bereits mehrmals geschrieben habe, halte ich das $\P$-$\NP$-Problem deswegen f\"{u}r besonders schwierig, weil wahrscheinlich $\P \neq \NP$ gilt und es aber sehr viel schwieriger ist zu beweisen, dass etwas nicht gilt, als das Gegenteil zu beweisen. Denn dass etwas nicht gilt, ist gleichbedeutend damit, dass etwas nicht existiert, und wie soll man beweisen, dass etwas nicht existiert?
\\
\\ Nehmen wir das bekannte Raben-Beispiel: Die Aussage ``Alle Raben sind schwarz'' ist logisch \"{a}quivalent zur Aussage ``Es existiert nichts, das ein Rabe und zugleich nicht schwarz ist''. Das kann man in der Sprache der Aussagenlogik so ausdr\"{u}cken:
\\
\\ $\neg \exists x R(x) \wedge \neg s(x)$.
\\
\\ Diese Aussage ist logisch \"{a}quivalent zur Aussage
\\
\\ $\forall x \neg s(x) \to \neg R(x)$.
\\
\\ Zum Beweis formen wir die Aussage Schritt f\"{u}r Schritt um:
\\
\\ $\neg \exists x R(x) \wedge \neg s(x)$
\\ $\equiv \forall x \neg (R(x) \wedge \neg s(x))$
\\ $\equiv \forall x \neg R(x) \vee s(x)$
\\ $\equiv \forall x R(x) \to s(x)$ (das ist die direkte \"{U}bersetzung von ``Alle Raben sind schwarz'')
\\ $\equiv \forall x \neg s(x) \to \neg R(x)$.
\\
\\ Bei dieser Umformung haben wir zuerst davon Gebrauch gemacht, dass jede Existenzaussage \"{u}ber einen Term A eine negierte Allaussage \"{u}ber Nicht-A darstellt, dann davon, dass eine negierte Konjunktion \"{a}quivalent ist zu einer Disjunktion der Negationen der Einzelaussagen, dann von der M\"{o}glichkeit, Implikationen als Disjunktionen auszudr\"{u}cken und zum Schluss von der Tatsache, dass die so genannte Kontraposition einer Implikation zu dieser logisch \"{a}quivalent ist.
\\
\\ Daraus ergibt sich, dass wir die Aussage ``Alle Raben sind schwarz'' beweisen k\"{o}nnten, wenn wir alle nicht-schwarzen Objekte kennten und zeigen k\"{o}nnten, dass es sich bei keinem von ihnen um einen Raben handelt.
\\
\\ Im Fall des $\P$-$\NP$-Problems lautet die zu beweisende Aussage: ``Es gibt kein $\NP$-vollst\"{a}ndiges Problem, das Element der Menge $\P$ ist.'' Diese Aussage k\"{o}nnte also bewiesen werden, wenn es m\"{o}glich w\"{a}re, alle Probleme, die Elemente der Menge $\P$ sind, aufzuz\"{a}hlen und f\"{u}r jedes dieser Probleme zu zeigen, dass es nicht $\NP$-vollst\"{a}ndig ist. Die Aussage $\P \neq \NP$ k\"{o}nnte auch bewiesen werden, wenn man eine Eigenschaft f\"{a}nde, die allen Problemen in $\P$ inh\"{a}rent ist, aber die kein $\NP$-vollst\"{a}ndiges Problem aufweist.
\\
\\ Dar\"{u}ber hinaus sollte man aber nicht vergessen, dass es gar nicht notwendig ist, eine zu $\P \neq \NP$ logisch \"{a}quivalente Aussage zu beweisen, um $\P \neq \NP$ zu beweisen. Es ist auch m\"{o}glich, $\P \neq \NP$ zu beweisen, indem man eine Aussage beweist, die $\P \neq \NP$ impliziert. Eine solche Aussage zu finden, erfordert freilich ein wenig Kreativit\"{a}t.
\\
\\ Wenn wir uns die Aussage
\\
\\ $\forall x \neg s(x) \to \neg R(x)$
\\
\\ ansehen, dann ist jedenfalls klar, dass gilt:
\\
\\ $(\forall x \neg R(x)) \to (\forall x \neg s(x) \to \neg R(x))$.
\\
\\ Im Kontext des $\P$-$\NP$-Problems w\"{u}rde dies bedeuten: Wenn es gar keine $\NP$-vollst\"{a}ndige Probleme g\"{a}be, dann w\"{a}re bewiesen, dass kein Problem, das in $\P$ liegt, $\NP$-vollst\"{a}ndig sein kann. Das ist trivial und bringt uns nichts, denn wir wissen ja, dass es $\NP$-vollst\"{a}ndige Probleme gibt.
\\
\\ Wir m\"{u}ssten also eine wahre Aussage finden, die die zu beweisende Aussage impliziert. Wenn man das Problem aber nur aussagenlogisch betrachtet und nicht die Eigenschaften von Problemen in $\P$ und von $\NP$-vollst\"{a}ndigen Problemen ber\"{u}cksichtigt, wird man meines Erachtens keine finden. Wir m\"{u}ssen also auf jeden Fall untersuchen, was Elemente der Menge $\P$ sonst noch auszeichnet au\ss{}er der trivialen Eigenschaft, dass sie in polynomieller Zeit in Bezug auf die Gr\"{o}\ss{}e der Eingabedaten gel\"{o}st werden k\"{o}nnen.
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\newpage

\begin{center}
\Large \textbf{Erratum}
\end{center}
\normalsize In MATHEMATIQ Ausgabe 2 wurde ein Beispiel f\"{u}r eine kontextfreie Sprache gebracht, die nicht zugleich regul\"{a}r ist. Dieses Beispiel ist ung\"{u}ltig, die Sprache l\"{a}sst sich n\"{a}mlich durch den regul\"{a}ren Ausdruck \textit{(a* b*)*} ausdr\"{u}cken, ist also sehr wohl regul\"{a}r. Dieser Fehler ist mir beim \"{U}bersetzen des Artikels ins Englische aufgefallen. In der englischen Fassung in MATHEMATIQ Ausgabe 10 (Sonderausgabe) habe ich deswegen ein anderes Beispiel gebracht; dieses Beispiel stellt tats\"{a}chlich eine kontextfreie Sprache dar, die nicht zugleich regul\"{a}r ist.
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\end{document}
