Das Folgende setzt die Mengenlehre voraus und beantwortet für \(k, m, n \in {}^{\nu}\mathbb{N}^*\) die Fragen: Wie lassen sich \(n = {\epsilon}^{\sigma} \le k^m\) im Stellenwertsystem zur Basis \(k\) kodierte Werte in \(\mathcal{O}(1)\) sortieren? Wie lassen sich zwei Matrizen \(\in {}^{\nu}\mathbb{R}^{n \times n}\) in \(\mathcal{O}(\sigma)\) multiplizieren? Wie lässt sich das Minimal- bzw. Maximalgerüst eines Graphen mit \(n\) Knoten in \(\mathcal{O}(\sigma)\) berechnen? Was ist die Antwort auf das Halteproblem? Warum gilt \(P = NP\)?
Sei der Speicher teilweise in Form eines Binomial-Baumes der Ordnung \(k\) mit \(k^{\grave{m}}\) Speicherplätzen organisiert, wobei \(k^{\grave{m}} = 2^h\) mit \(h \in {}^{\nu}\mathbb{N}\) gelte. Jeder Speicherplatz sei in der Lage einen zu sortierenden Wert komplett aufzunehmen und jeder Kante entspreche eine Datenleitung. Ein fortlaufend mehrfachen Werten angehängter Index bildet zusammen mit dem alten Wert den neuen. Jeder \(j\)-te Zwischenknoten korrespondiert hierarchisch mit der \(j\)-ten Stelle zur Basis \(k\) des zu sortierenden Wertes.
Speichern die Blätter statt der Werte deren Adressen (in einem Schritt) lassen sie sich (in einem weiteren) sortiert in die Wurzel zurückholen. Hierbei werden sie maximal so weit in den Baum geschoben, bis sie sich trennen. Geht ein Wert durch einen Zwischenknoten, setzt dieser sein Bit auf 1, aber auf 0, falls der Zwischenknoten keinen auszulesenden Nachfolger hat. Die Sortierreihenfolge bestimmt den ersten Wert. Speichern, Nachfolger prüfen, Bits maskieren und auslesen dauert \(\mathcal{O}(n)\).
Hier und im Folgenden wird eine Speicherarchitektur mit autonomen Speichereinheiten verwendet, die über einfache rechnerische Möglichkeiten verfügt. Sie lässt sich auch durch zusammengeschaltete verteilte Rechner simulieren. Die Komplexität erhöht sich durch Einsortieren eines zusätzlichen Wertes um \(\mathcal{O}(\sigma)\), da dies einer binären Suche entspricht. Sie ist antiproportional zur Anzahl der Baumknoten im Speicher. Das Verwenden von \(d \in {}^{\nu}\mathbb{N}^*\) Datenleitungen verringert sie um den Faktor \(\tilde{d}\).
Belegen die Werte das \(g\)-fache eines Speicherplatzes, erhöht sie sich um den Faktor \(g\). Enthält der Speicher keinen Binomial-Baum der Ordnung \(k\), erhöht sie sich um den Faktor \({_k}n\), weil jeder Zwischen- knoten zu einem Wert zu lesen ist. Ein anderweitiges Nutzen der ersten \(k^p\) Speicherplätze mit \(p \in {}^{\nu}\mathbb{N}\) erfordert ein Durchsuchen aller Zwischenknoten der \(p\)-ten Stufe. Die Komplexität erhöht sich bei gut gefülltem Speicher marginal, andernfalls um den Worst-Case-Faktor \(\mathcal{O}(k^p)\).
Die zu multiplizierenden Matrizen sind so quadratweise je \(n\)-fach in einem Speicherwürfel abzulegen, dass jede Speichereinheit zwei Werte multipliziert und jeder Eintrag der Produktmatrix als Summe mit \(n\) Summanden in \(\mathcal{O}(\sigma)\) bestimmt wird (Vektorrechner). Matrixmultiplikation lässt sich auch über adressierte schwärmende Einträge realisieren. Tensorprodukte lassen sich effizient durch \(n\)-Speicherwürfel abbilden, die durch entsprechende Datenleitungen im dreidimensionalen Raum verbleiben.
Der optimale Sortieralgorithmus Bitsort sortiert stabil mit der Zeitkomplexität \(\mathcal{O}(n)\) und benötigt \(\mathcal{O}(n)\) zusätzlichen Speicherplatz. Voraussetzungen: Je zwei Werte liegen als Bitfolge vor, lassen sich in \(\mathcal{O}(1)\) vergleichen und ebenso deren sämtliche Bits abarbeiten. Ferner sei der Speicher teilweise als Binärbaum realisiert und der Weg von Wurzel bis Blatt kann ebenfalls in \(\mathcal{O}(1)\) durchlaufen werden.
Ist \(p \in {}^{\nu}\mathbb{N}^*\) die Anzahl der parallelen Schritte für paralleles Bitsort, so ist die Zeitkomplexität \(\mathcal{O}(\tilde{p} n)\). Jedes Einfügen in den stets sortierten Baum bzw. Ausgeben eines Wertes hat die Zeitkomplexität \(\mathcal{O}(1)\). Der Speicher sei mit folgender Intelligenz versehen: Jeder Baumknoten speichert den ihn erreichenden Wert selbständig und kann ihn an den nächsten Baumknoten weitergeben, wenn er schon besucht wurde, bzw. andernfalls seine Adresse an die Zentraleinheit zurückgeben. Der Wurzel entspricht kein Bitwert.
Begonnen wird bei dem höchstwertigen Bit eines Wertes. Jedes seiner nacheinander abgearbeiteten Bits bestimmt den nächsten Knoten innerhalb des Binärbaumes. Wurden alle Bits abgearbeitet oder ergibt sich ein Unterschied zum verglichenen Bit und wurde der zugehörige Knoten noch nicht besucht, speichert der folgende Knoten ggf. die nicht im Baum liegende Adresse der restlichen Bitkette des Wertes bzw. die Anzahl der Werte für diesen Knoten bei unerheblicher Reihenfolge gleicher Werte.
Die Zeitkomplexität aller Verfahren, die Werte mit einer Bitlänge \(b = q a \in {}^{\nu}\mathbb{N}^*\) bei Adresslänge \(a \in {}^{\nu}\mathbb{N}^*\) sortieren, erhöht sich pro Wert von \(\mathcal{O}(1)\) auf \(\mathcal{O}(q)\). Ist \(r\) der Durchschnittswert von \(q\), ist in der Zeitkomplexität des Sortierverfahrens mindestens ein \(\mathcal{O}(n)\) durch \(\mathcal{O}(r n)\) zu ersetzen. Ist \(s \in {}^{\nu}\mathbb{N}^*\) die durchschnittliche Anzahl der verschiedenen (!) Werte, die in einem Bucket nach Sortierung bis Bitlänge \(a\) landen und deren Bitlänge größer als \(a\) ist, so beträgt die Zeitkomplexität des Verfahrens \(\mathcal{O}(({_\epsilon}s + r) n)\).
Dabei werden die erwähnten Werte eines Buckets pro Bucket in einem AVL-Baum abgelegt oder in einem B-Baum bei Ablage in einem zum Hauptspeicher relativ langsamen externen Speicher. Dort wird jeweils nur mit dem signifikanten Teilwert der Adresslänge eines Wertes gearbeitet. Der Verzicht auf vollständig sortierte Werte nach jedem Abarbeiten eines Wertes reduziert die komplette Sortierung durch Verwendung von zwei Hauptspeicherbereichen zeitlich auf \(\mathcal{O}(r n)\).
Der zweite Hauptspeicherbereich wird nach jedem Durchlauf gelöscht, um für den nächsten Durchlauf zur Verfügung zu stehen, bis ein Bucket abgearbeitet ist. In den ersten Hauptspeicherbereich werden stets nur die Adressen in der aktuellen Sortierreihenfolge zurückgeschrieben, bevor die Werte mit gleichem soeben abgearbeitetem Teilwert weiter sortiert werden. Für den schnellen Zugriff auf jeden Teilwert ist jeder Wert zusammenhängend im Speicher abzulegen.
Die Verwendung des \(\mathcal{O}(r n)\)-Verfahrens für die Stammdaten und des \(\mathcal{O}(({_\epsilon}s + r) n)\)-Verfahrens für die Bewegungsdaten kombiniert beide gut. Damit lassen sich insbesondere schnell Tabellenindizes anlegen. Bei umfangreichen Tabellen macht es einen deutlichen Unterschied, ob ein Index in \(\mathcal{O}(r n)\) statt in \(\mathcal{O}(r\sigma n)\) angelegt wird und sich dann ein Wert durchschnittlich in \(\mathcal{O}({_\epsilon}s + r)\) statt in \(\mathcal{O}(\sigma + r)\) oder schlechter suchen lässt. Sortieren durch Mischen sortierter Listen ist ebenfalls in \(\mathcal{O}(r n)\) möglich.
Diskussion von Bitsort: Es ist unter den angegebenen Voraussetzungen optimal sowie für die parallele Programmierung, den schnellen laufenden Aufbau von Tabellenindizes in Datenbanken und die Suche darin gut geeignet. Seine Hardwareimplementierung ist eher ungewöhnlich.
Sei \(n \in {}^{\nu}\mathbb{N}^*\) die Anzahl der Knoten eines endlichen schlichten zusammenhängenden Graphen.
(Ist er nicht schlicht, lässt ein Aussortieren in \(\mathcal{O}(n)\) nur die kleinste parallele Kante und keine Schlingen zu. Ist er nicht zusammenhängend, werden in \(\mathcal{O}(n)\) alle isolierten Knoten entfernt.) Bei Ausschluss negativer Gewichte benötigt der Algorithmus von Dijkstra \(\mathcal{O}(n)\) Schritte für jeden minimalen Weg in dem Graphen, da Sortieren sowie paralleles Addieren und Vergleichen in \(\mathcal{O}(1)\) möglich ist.
Dessen Minimal- oder Maximalgerüst lässt sich in \(\mathcal{O}(\sigma n)\) oder gar in \(\mathcal{O}(\sigma)\) berechnen: Die Kanten eines Knotens lassen sich parallel in \(\mathcal{O}(n)\) bzw. \(\mathcal{O}(1)\) sortieren. Seien alle Kanten zu Beginn weiß gefärbt. Jeder Knoten hängt die kleinere und dann die größere Zahl der beteiligten Knoten der Kante mit dem kleinsten Gewicht aller weiß gefärbten Kanten, die von ihm ausgehen, an dieses Bit für Bit als Wert an. Er speichert den kleinsten Wert, der ihn erreicht. Dies ist in \(\mathcal{O}(n)\) bzw. \(\mathcal{O}(1)\) möglich.
Das Schwarzfärben der Kanten zwischen jeweils zwei Knoten desselben Minimalgerüsts benötigt maximal die gleiche Zeit. Jeder Knoten hat dann einen nächsten Nachbarknoten. Ein Fortfahren mit den weiß gefärbten Kanten in \(\mathcal{O}(\sigma)\) Schritten kann den kleinsten Wert eines Minimalgerüsts in \(\mathcal{O}(n)\) bzw. \(\mathcal{O}(1)\) bestimmen, bis das gesamte Minimalgerüst in \(\mathcal{O}(\sigma n)\) bzw. \(\mathcal{O}(\sigma)\) entstanden ist. Für ein Maximalgerüst werden alle Kantengewichte von einer hinreichend großen Konstanten subtrahiert.
Haltesatz: Um ein festes \(r_m\) der Zahl \(0,r_{1}r_{2}…r_{m}\) zu erreichen, hält ein Programm für beliebige (Pseudo-) Zufallszahlen \(r_j \in {}^{\nu}\mathbb{N}\) mit \(k \in {}^{\nu}\mathbb{N}^{*}\) Stellen und Basis \(p := 2^k\) in \(m \in \mathbb{N}^{*}\) Schritten mit der Wahrscheinlichkeit \(\tilde{p}\).
Beweis: Dies ist ein optimales Ergebnis der Wahrscheinlichkeitsrechnung1vgl. Knuth, Donald Ervin: The Art of Computer Programming Volume 2; 3rd Ed.; 1997; Addison Wesley; Reading, S. 10 – 40.\(\square\)
Bemerkung: Zufall ist unentscheidbar. Damit existieren Programme, die mit beliebiger Wahrscheinlichkeit halten, und es folgen die Gödelschen Unvollständigkeitssätze. Der Gödelsatz \glqq Ich bin nicht beweisbar.\grqq{} ist insofern sophistisch, als er das Scheinargument Petitio Principii ex negativo aufweist. Um das Halteproblem zu lösen, ist ein Selbstbezug unsinnig, der ein Halten gleichzeitig gebietet und verbietet. Die Selbstreferenz macht das Diagonalargument für das Halteproblem unzulässig.
Satz: Ist \(\mathcal{L}\) die Menge aller (Typ-0-) Sprachen \(L_k\) aus endlichen Wörtern mit Maximallänge \(\nu\) für mittendliches \(|\mathcal{L}| = 2^{({\nu}^{\grave{\nu}}-1)/\acute{\nu}}\) (unter Anwendung der GR) und \(k \in \{1, …, |\mathcal{L}|\}\), gilt \(P = NP = \mathcal{L}\).
Beweis: Da sich jede deterministische Turingmaschine auch als nichtdeterministisch auffassen lässt2vgl. Hoffmann, Dirk W.: Theoretische Informatik; 4., akt. Aufl.; 2018; Carl Hanser; München, S. 162, 318 and 361 f., gilt \(P \subseteq NP\). Es enthält \(P\) alle linearen Sprachen \(L_k\) und \(NP\) nur solche.\(\square\)
© 2006-2019 by Boris Haase