% 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 21
\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 einundzwanzigste 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 wieder 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{K\"{o}nnte man das $\P$-$\NP$-Problem so l\"{o}sen?}
\end{center}
\normalsize Als ich vor einigen Tagen meinen drei\ss{}igsten Geburtstag feierte, w\"{u}nschte mir ein Gratulant, mir m\"{o}ge es in diesem neuen Lebensjahr endlich gelingen, das $\P$-$\NP$-Problem (siehe fr\"{u}here Ausgaben von MATHEMATIQ) zu l\"{o}sen. Daraufhin war ich wieder angestachelt und habe mich bis Mitternacht mit dem Problem besch\"{a}ftigt, obwohl ich am n\"{a}chsten Tag wieder arbeiten musste. Dabei kam die folgende \"{U}berlegung heraus:
\\
\\ Ein Problem ist genau dann in $\NP$, wenn es einen polynomiellen Algorithmus (in Bezug auf die Gr\"{o}\ss{}e der Eingabedaten) gibt, der \"{u}berpr\"{u}ft, ob eine gegebene L\"{o}sung korrekt ist.
\\
\\ Ein Problem ist genau dann in $\P$, wenn es in $\NP$ ist und zus\"{a}tzlich die Anzahl der L\"{o}sungen, die \"{u}berpr\"{u}ft werden m\"{u}ssen, so dass mit hundertprozentiger Sicherheit die korrekte L\"{o}sung darunter ist, polynomiell ist (ebenfalls in Bezug auf die Gr\"{o}\ss{}e der Eingabedaten).
\\
\\ Ich definiere:
\\
\\ L\"{o}sungsraum: ist die Anzahl der L\"{o}sungen, die es \"{u}berhaupt geben kann, egal ob korrekt oder nicht.
\\
\\ Suchraum: ist die Anzahl der L\"{o}sungen, die unbedingt durchsucht werden m\"{u}ssen, damit mit hundertprozentiger Sicherheit die korrekte L\"{o}sung darunter ist (ohne Raten und ohne vorherige Kenntnis der korrekten L\"{o}sung).
\\
\\ Die Frage ist, ob es Probleme gibt, die in $\NP$, aber nicht in $\P$ liegen.
\\
\\ Bekannt ist: Es gibt $\NP$-vollst\"{a}ndige Probleme; nur wenn ein $\NP$-vollst\"{a}ndiges Problem in $\NP$, aber nicht in $\P$ liegt, gibt es Probleme, die in $\NP$, aber nicht in $\P$ liegen.
\\
\\ Ein $\NP$-vollst\"{a}ndiges Problem ist $k$-$\SAT$: Gegeben sind $n$ boolesche Variablen (k\"{o}nnen die Werte wahr oder falsch annehmen), diese kommen in $c$ Clauses (Disjunktionen) vor, jeweils $k$ Variablen pro Clause; alle Clauses sind miteinander durch Konjunktion \"{u}berpr\"{u}ft.
\\
\\ Ich m\"{o}chte zeigen, dass der Suchraum bei $k$-$\SAT$ nicht polynomiell und daher $k$-$\SAT$ nicht in $\P$ enthalten ist.
\\
\\ Der L\"{o}sungsraum betr\"{a}gt $2^n$, da jede Variable entweder wahr oder falsch sein kann, also genau zwei Werte annehmen kann. Der tats\"{a}chliche Suchraum ist kleiner als $2^n$, aber im allgemeinen Fall nicht polynomiell. Der Grund: Es gibt keine andere M\"{o}glichkeit vorzugehen, als einer Variablen einen Wert zuzuweisen und dann zu schauen, wie sich das auf die anderen Variablen auswirkt. Wenn $k$-$\SAT$ in $\P$ w\"{a}re, dann m\"{u}sste es in jeder Formel die gleiche Anzahl von Variablen geben, deren Wert man festlegen muss, so dass sich die Werte aller anderen Variablen ergeben. Wenn das $t$ Variablen sind, dann ist der Suchraum $n \choose t$. Wenn $t$ konstant ist, ist das polynomiell. $t$ ist aber nicht konstant. Vielmehr stellt die Anzahl der Clauses eine obere Schranke f\"{u}r t dar. $t$ kann also unter Umst\"{a}nden so gro\ss{} sein wie die Anzahl der Clauses. Da die Anzahl der Clauses bei $k$-$\SAT$ aber variabel ist, ist der Suchraum nicht polynomiell (bei der Angabe einer oberen Schranke k\"{a}me $n$ im Exponent vor).
\\
\\ Bei der Diskussion dar\"{u}ber im \"{o}sterreichischen Informatik-Forum zeigte sich, dass die Schwachstelle an diesen Ausf\"{u}hrungen in der Aussage ``Es gibt keine andere M\"{o}glichkeit vorzugehen, als einer Variablen einen Wert zuzuweisen und dann zu schauen, wie sich das auf die anderen Variablen auswirkt'' besteht. Diese Aussage ist unbewiesen. Offenbar ist das aber auch die einzige Schwachstelle - zumindest konnte keine weitere gefunden werden. Dass ein Problem, das in $\NP$, aber nicht in $\P$ liegt, einen nicht-polynomiellen Suchraum haben muss, l\"{a}sst sich leicht beweisen; es ist eine logische Folgerung aus obigen Definitionen. Die Schwierigkeit besteht blo\ss{} darin zu zeigen, dass es nicht m\"{o}glich ist, den Suchraum zu generieren, indem man einer Anzahl von Variablen einen Wert zuweist, wobei diese Anzahl der Variablen h\"{o}chstens polynomiell in Bezug auf die Gesamtzahl der Variablen ist, sondern dass dieses Verh\"{a}ltnis nicht-polynomiell ist. Einige Kollegen meinten, ich w\"{a}re der L\"{o}sung des Problems nicht n\"{a}hergekommen, sondern h\"{a}tte es nur auf eine andere Ebene verlagert. Wie dem auch sei, vielleicht ist das Problem auf dieser Ebene leichter l\"{o}sbar.
\\
\\ In diesem Zusammenhang m\"{o}chte ich vorschlagen, vielleicht gar nicht \"{u}ber $\SAT$ zu diskutieren, sondern \"{u}ber ein anderes, anschaulicheres Problem:
\\
\\ Gegeben ist eine Konstante $c$. Gesucht sind $n$ nat\"{u}rliche Zahlen ungleich 1 (denn 1 ist das neutrale Element der Multiplikation, was das Problem trivial machen w\"{u}rde), die miteinander multipliziert diese Konstante $c$ ergeben.
\\
\\ Dieses Problem scheint mir genauso komplex wie $\SAT$ zu sein, es scheint mir aber einfacher zu analysieren zu sein. Ich w\"{u}sste f\"{u}r dieses Problem auch keine andere M\"{o}glichkeit, als nach einem Algorithmus vorzugehen, der f\"{u}r $n$ - 1 Variablen die Werte durchiteriert, wobei sich der Wert der $n$-ten Zahl ergeben w\"{u}rde. Vielleicht k\"{o}nnte man f\"{u}r dieses Problem leichter als f\"{u}r $\SAT$ zeigen, dass es gar nicht anders gel\"{o}st werden kann. Vorschl\"{a}ge dazu w\"{a}ren sehr willkommen.
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\end{document}
