Informatik & KIPreprintTheorie3 Min. Lesezeit

SORTIEREN MIT VERBOTENEN VERGLEICHEN, FAST GENAUSO SCHNELL

Um n Objekte in eine Reihenfolge zu bringen, indem man sie jeweils zu zweit vergleicht, sind etwa n log n Vergleiche sowohl nötig als auch ausreichend. Das setzt aber voraus, dass sich zwei beliebige Objekte vergleichen lassen.

Oft geht das nicht. Die Autoren leihen sich ein Beispiel aus einer Arbeit von 2011: Mehrere Kandidaten bewerben sich auf dieselbe Stelle, jeder mit Referenzen. Zwei Kandidaten lassen sich nur vergleichen, wenn eine Referenzperson beide kennt. Die erlaubten Vergleiche bilden ein Netz, einen Graphen: Jedes Objekt ist ein Punkt, jeder zulässige Vergleich eine Verbindung. Die wahre Reihenfolge ist verborgen, aber der Graph enthält sie garantiert, als Pfad, der jedes Objekt mit dem nächsten verbindet. Die Frage: Wie viele Vergleiche braucht man, um die Reihenfolge zu rekonstruieren? Das ist verallgemeinertes Sortieren (generalized sorting).

Warum die üblichen Tricks versagen

Die klassischen Algorithmen leben von der Wahlfreiheit. QuickSort wählt ein „Pivotelement“ und vergleicht es mit den meisten anderen Objekten, doch ein beliebiger Graph hat vielleicht kein Objekt, das mit den meisten anderen verbunden ist. MergeSort teilt die Objekte in Gruppen auf und sortiert jede einzeln, doch eine Gruppe lässt sich womöglich nicht für sich allein sortieren: Zwei Objekte, die in der endgültigen Reihenfolge Nachbarn sind, müssen innerhalb der Gruppe nicht verbunden sein. Grundsätzlicher noch: Beim gewöhnlichen Sortieren gibt es immer einen verfügbaren Vergleich, der einen guten Teil der möglichen Reihenfolgen ausschließt; bei eingeschränkten Vergleichen gibt es womöglich keinen.

Die Fortschritte kamen langsam. 2011 fanden Zhiyi Huang, Sampath Kannan und Sanjeev Khanna eine Methode mit etwa n¹·⁵ Vergleichen, bis auf logarithmische Faktoren, und diese Schranke hat sich für beliebige Graphen seither gehalten. Sie fragten sogar, ob das Problem grundsätzlich schwerer sein könnte als gewöhnliches Sortieren und n hoch einer Potenz über 1 erfordern würde.

Erst vorhersagen, dann reparieren

Sanjeev Khanna von der New York University, Aaron Putterman von der Harvard University und Junkai Song, ebenfalls von der New York University, beantworten diese Frage nun: nein. Ihr randomisierter Algorithmus sortiert mit durchschnittlich etwa n log⁴ n Vergleichen, auf jedem Graphen – nur wenige logarithmische Faktoren über dem gewöhnlichen Sortieren. Und er sei, schreiben sie, „relativ einfach“. Der Gewinn ist allerdings theoretisch: Die Konstanten des Beweises sind enorm (Faktoren wie 2³²), sodass sich der Vorteil erst bei sehr großem n zeigt.

Er baut auf einem bekannten Ergebnis auf: Wenn dir jemand eine Vermutung über die Richtung jeder Verbindung gibt, die bei w von ihnen falsch liegt, lässt sich die Reihenfolge mit etwa n log n + w Vergleichen rekonstruieren. Die Aufgabe besteht also darin, mit wenigen Vergleichen eine Vermutung mit wenigen Fehlern zu erzeugen. Die entscheidenden Schritte:

  • Eine grobe erste Vermutung. Vergleiche eine Zufallsstichprobe verbundener Paare und wähle irgendeine Reihenfolge, die zu den Antworten passt. Sie enthält viele Fehler, aber nicht zu viele.
  • Fehler isolieren statt beheben. Statt falsche Vermutungen zu korrigieren, sucht der Algorithmus Teile des Graphen, in denen Fehler dichter liegen als im Durchschnitt, und legt sie beiseite. Jede Runde senkt die verbleibenden Fehler im Erwartungswert um den Faktor vier.
  • Später zurückkommen. Die beiseitegelegten Verbindungen werden in einer späteren Phase behandelt. Jede Phase erledigt mindestens die Hälfte der noch offenen Verbindungen, sodass etwa zwanzig Phasen für eine Million Verbindungen genügen.

Ein Beweis, mit Maschinen gefunden

Die KI-Offenlegung der Arbeit ist ungewöhnlich ausführlich. Sie hält fest, dass ChatGPT 6-Astra „wesentlich für den Beweis der verbesserten Schranken“ war. Ein Modell fand zunächst einen Algorithmus mit etwa n¹·³³ Vergleichen und kam dann nicht weiter. Die Autoren verbesserten ihn auf n¹·²; dann fanden Modelle, über mehrere Wochen hinweg dutzendfach angestoßen, nacheinander Verbesserungen – n^(10/9), n^(17/16), n^(19/18) –, bevor sie den nahezu linearen Algorithmus erreichten. Die Autoren fügen hinzu, es sei unklar, ob ihr eigener Zwischenschritt für diese letzte Entdeckung wesentlich war.

Was noch offen ist

Das Ergebnis zählt Vergleiche, nicht Rechenzeit: In der vorliegenden Form läuft der Algorithmus nicht in Polynomialzeit, die Methode von 2011 dagegen schon. Die Autoren nennen drei offene Fragen: ob sich die verbleibenden logarithmischen Faktoren beseitigen lassen, ob ein Algorithmus ohne Zufall ebenso gut abschneiden kann und ob ein effizienter Algorithmus dieselbe Zahl von Vergleichen erreichen kann – oder n¹·⁵ überhaupt unterbieten.