-Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft
-{\em nicht} hat, ist mit einem gegebenen Gegenbeispiel einfach möglich.
-Dieses Gegenbeispiel zu finden ist allerdings aufwendig.
-
-\todo{Wie findet man die Gegenbeispiele? Die {\em Entscheidung}, ob ein
-Netzwerk sortiert, ist doch NP-vollständig, also müsste doch das Finden eines
-Gegenbeispiels im Allgemeinen auch exponentialle Laufzeit haben..?}
-\todo{Wenn die {\em Entscheidung}, ob ein Netzwerk sortiert, NP-vollständig
-ist, müsse man dann nicht einen Zeugen für die Sortiereigenschaft angeben
-können?}
-
-\todo{$0-1$-Prinzip}
-
-Um zu überprüfen, ob ein gegebenes Komparatornetzwerk die Sortiereigenschaft
-besetzt, müssen nicht alle $n!$ Permutationen von $n$~unterschiedlichen Zahlen
-ausprobieren. Stattdessen reicht es zu überprüfen, dass das Netzwerk alle
-$2^n$~0-1-Folgen sortiert.
-
-Sortiernetzwerke:
-\begin{itemize}
-\item Ein Komparator-Netzwerk ist $\ldots$
-\item Ein Komparator-Netzwerk ist ein Sortiernetzwerk, wenn $\ldots$
-\item Die Frage nach der Sortiereigenschaft ist NP-vollständig.
-\end{itemize}
+\begin{figure}
+ \begin{center}
+ \input{images/09-e2-c24-allbut1.tex}
+ \end{center}
+ \caption{Ein \emph{Komparatornetzwerk} mit neun Eingängen und
+ 24~Komparatoren, die in 8~Schichten angeordnet sind. Das Netzwerk sortiert
+ alle Eingaben, bei denen das Minimum nicht auf dem mittleren Eingang liegt.}
+ \label{fig:09-e2-c24-allbut1}
+\end{figure}
+Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft {\em
+nicht} hat, ist mit einem gegebenen Gegenbeispiel einfach möglich. Das
+Komparatornetzwerk wird auf das Gegenbeispiel angewendet und anschließend wird
+überprüft, ob die Ausgabe sortiert ist. Ist sie es nicht heißt das, dass es
+mindestens eine Eingabefolge gibt, die nicht sortiert wird. Entsprechend der
+Definition handelt es sich bei dem \emph{Komparatornetzwerk} folglich
+\emph{nicht} um ein \emph{Sortiernetzwerk}. Ein solches Gegenbeispiel für ein
+gegebenes Komparatornetzwerk zu finden ist nach heutigem Kenntnisstand jedoch
+nicht \emph{effizient} möglich.
+
+Beispielsweise sortiert das im Rahmen dieser Arbeit entdeckte
+Komparatornetzwerk in Abbildung~\ref{fig:09-e2-c24-allbut1} viele der 362.880
+möglichen Eingabepermutationen. Mit dem Gegenbeispiel $(3, 5, 2, 1, 0, 7, 4,
+8, 6)$ lässt sich jedoch leicht beweisen, dass das Komparatornetzwerk die
+Sortiereigenschaft \emph{nicht} besitzt, da es in diesem Fall die Folge $(1,
+0, 2, 3, 4, 5, 6, 7, 8)$ ausgibt.
+
+Insgesamt gibt es $n!$~Permutationen von $n$~Elementen. Wenn ein
+Komparatornetzwerk die Sortiereigenschaft besitzt, bildet es alle diese
+Permutationen auf die sortierte Reihenfolge ab. Allerdings wächst $n!$
+über-exponentiell schnell, so dass ein Ausprobieren aller möglichen
+Permutationen schon bei 16~Leitungen praktisch nicht mehr zu bewerkstelligen
+ist.\footnote{1.307.674.368.000 Permutationen}
+
+\label{sect:0-1-prinzip}
+Glücklicherweise reicht es aus, alle möglichen 0-1-Folgen zu überprüfen, wie
+\textit{Donald~E. Knuth} in \cite{KNUTH} zeigt. Die Beweisidee ist folgende:
+Angenommen ein Komparatornetzwerk sortiert alle 0-1-Folgen und es gibt eine
+Permutation $E = (e_0, \dots, e_{n-1})$ beliebiger Zahlen, die nicht sortiert
+wird. Die Ausgabefolge sei $A = (a_0, \dots, a_{n-1})$. Sei $i$ eine Position
+in der Ausgabe, die die Sortierbedingung verletzt:
+\begin{displaymath}
+ a_0 \leqq a_1 \leqq \dots \leqq a_{i-1} > a_i \dots
+\end{displaymath}
+Die Eingabe kann mittels
+\begin{displaymath}
+ \hat{e}_j = \left\{
+ \begin{array}{cl}
+ 0 & e_j \leqq a_i \\
+ 1 & e_j > a_i
+ \end{array} \right.
+\end{displaymath}
+auf eine 0-1-Folge abgebildet werden, die entsprechen der Annahme vom
+Komparatornetzwerk sortiert wird. Allerdings verändert diese Abbildung das
+Verhalten jedes einzelnen Komparators nicht, so dass die Annahme auf einen
+Widerspruch geführt wird.
+
+Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der
+Komplexitätsklasse
+$\mathcal{O}\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist,
+ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\mathcal{O}(2^n)$
+verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein
+schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen,
+ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt,
+sind mit dieser Methode nur 65.536 Tests notwendig -- eine Zahl, die für
+aktuelle Prozessoren keine Herausforderung darstellt. Für die Überprüfung
+eines Komparatornetzwerks mit 32~Leitungen sind jedoch bereits etwa
+4,3~Millarden Tests notwendig, die einen Rechner durchaus mehrere Minuten
+beschäftigen.