% 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 27
\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 siebenundzwanzigste 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{\"{U}berlegungen zum $\P$-$\NP$-Problem}
\end{center}
\normalsize Wer die einschl\"{a}gigen Artikel in den vergangenen Ausgaben noch nicht gelesen hat, m\"{o}ge zuerst diese lesen.
\\
\\ Alle Probleme in $\P$ haben die Gemeinsamkeit, dass der Suchraum polynomiell ist, wenn man so vorgeht, dass man alle relevanten L\"{o}sungen durchprobiert und mit einem polynomiellen Algorithmus (der ja existiert, weil $\P$ eine Teilmenge von $\NP$ ist) \"{u}berpr\"{u}ft. Das bedeutet aber auch, dass der Suchraum maximal $c n^k$ verschiedene L\"{o}sungen enthalten kann, wenn $n$ die Gr\"{o}\ss{}e der Eingabedaten ist und $k$ und $c$ Konstanten. Sonst w\"{a}re er nicht polynomiell. Die Gr\"{o}\ss{}e der Datenstruktur, die gen\"{u}gt, um diesen Suchraum zu repr\"{a}sentieren, betr\"{a}gt daher $k \log n + \log c$ bit.
\\
\\ Ein jedes Problem in $\P$ erlaubt also, dass alle relevanten L\"{o}sungen in einer Anzahl von Bit dargestellt werden k\"{o}nnen, die sich zur Gr\"{o}\ss{}e der Eingabedaten logarithmisch verh\"{a}lt, also viel kleiner als die Eingabedaten ist.
\\
\\ Ein Beispiel daf\"{u}r: Das Problem, ob zwei Zahlen $a$ und $b$ einander teilerfremd sind, ist in $\P$, denn ein gemeinsamer Teiler der beiden Zahlen muss zwischen 1 und $a$ liegen, wenn $a$ die kleinere der beiden Zahlen ist. Man muss also nur $a$ verschiedene L\"{o}sungen durchprobieren. Das Problem ist polynomiell. Die Zahl $a$ wird durch $1 + \log a$ bit dargestellt.
\\
\\ Ein etwas komplexeres Beispiel: Das Problem 2-COL, das sich damit besch\"{a}ftigt, ob ein Graph mit nur zwei Farben f\"{a}rbbar ist, so dass zwei miteinander verbundene Knoten zwei verschiedene Farben zugewiesen bekommen, ist in $\P$. Die Datenstruktur der L\"{o}sung scheint zun\"{a}chst so beschaffen zu sein, dass es $2^n$ verschiedene Zahlenwerte gibt, wobei $n$ die Anzahl der Knoten ist. Schlie\ss{}lich liegt es nahe, dass man eine Datenstruktur aus $n$ bit verwendet, wobei jedes Bit entweder 0 oder 1 sein kann, je nachdem, welche Farbe dem Knoten zugewiesen wurde. Tats\"{a}chlich aber l\"{a}sst sich jede L\"{o}sung eindeutig darstellen, indem ich einfach nur die Nummer eines Knoten abspeichere, der eine bestimmte Farbe zugewiesen bekommt - denn alle anderen Farbwerte k\"{o}nnen von einem Algorithmus in polynomieller Zeit ermittelt werden. Es geht sogar noch einfacher: Ich kann auch einen Anfangsknoten festlegen und einfach die Farbe abspeichern, die er zugewiesen bekommt, also 0 oder 1. Eine Instanz dieses Problems, die nicht mit zwei Farben f\"{a}rbbar ist, hat als L\"{o}sungsmenge die leere Menge.
\\
\\ Das hei\ss{}t: W\"{a}re $\P$ = $\NP$, k\"{o}nnte ich dies beweisen, indem ich f\"{u}r ein $\NP$-vollst\"{a}ndiges Problem eine Darstellung der L\"{o}sungen f\"{a}nde, deren Gr\"{o}\ss{}e $k \log n + \log c$ bit betr\"{a}gt. Nehme ich ein $\NP$-vollst\"{a}ndiges Problem, zum Beispiel $\SAT$, her, m\"{u}sste ich zeigen k\"{o}nnen, dass ich jede L\"{o}sung so komprimieren kann, dass sich die Gr\"{o}\ss{}e der komprimierten L\"{o}sung im Vergleich zur Originall\"{o}sung asymptotisch betrachtet logarithmisch verh\"{a}lt. Das ist nur dann m\"{o}glich, wenn ich bei einer Anzahl von $n$ zu ermittelnden Werten bereits durch die Ermittlung von $\log n$ Werten alle anderen Werte eindeutig bestimmen kann. Wenn ich also zwei Variablen in $\SAT$ habe, muss die Angabe des Wertes einer Variablen gen\"{u}gen, um den Wert der zweiten Variablen eindeutig zu bestimmen; bei drei bis vier Variablen m\"{u}ssen zwei Werte gen\"{u}gen, bei f\"{u}nf bis acht Variablen drei Werte usw. Wenn ich f\"{u}r eine einzige konkrete Instanz von $\SAT$ beweisen kann, dass sie auf diese Weise nicht l\"{o}sbar ist, dann ist damit $\P \neq \NP$ bewiesen. Jedenfalls zumindest sofern meine hier dargelegte ``line of reasoning'' stimmt.
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\end{document}
