Informatik & KIPreprintTheorie3 Min. Lesezeit

DAS TEMPOLIMIT FÜR DIE SUCHE NACH CLIQUEN FÄLLT NACH 40 JAHREN

Stell dir ein soziales Netzwerk mit n Personen vor. Gibt es eine Gruppe von k unter ihnen, die sich alle gegenseitig kennen? In der Informatik heißt eine solche Gruppe k-Clique, und eine zu finden ist ein klassisches Problem mit unzähligen Anwendungen. Der naive Ansatz prüft jede mögliche Gruppe von k Personen, grob n^k Stück — aussichtslos für große Netzwerke.

Ein Trick von 1985 und eine lange Herausforderung

Vor mehr als 40 Jahren fanden Jaroslav Nešetřil und Svatopluk Poljak eine Abkürzung. Sie verwandelten die Suche nach einer k-Clique in die Suche nach einem Dreieck in einem größeren Graphen, was sich wiederum erledigen lässt, indem man Matrizen multipliziert, große Zahlentabellen. Der Aufwand hängt von ω ab, dem Exponenten der Matrizenmultiplikation: Ihre Methode braucht etwa n^(ωk/3) Schritte. Niemand kennt ω genau. Es ist mindestens 2, und der Artikel nennt eine neuere obere Schranke von 9/4.

Der Exponent dieser Methode von 1985 wurde nie unterboten. 2004 forderte Gerhard Woeginger die Fachwelt heraus, es für irgendein festes k besser zu machen; mehr als zwei Jahrzehnte vergingen. Unterdessen wurde die k-Clique-Hypothese — dass n^(ωk/3) im Wesentlichen das Bestmögliche ist — zu einem Fundament der „feinkörnigen Komplexitätstheorie“ (fine-grained complexity). Die Forschung stützte sich darauf, um zu argumentieren, dass sich viele andere Probleme, vom Parsen von Grammatiken bis zur Analyse komprimierter Daten, ebenfalls nicht schneller lösen ließen.

Ein bewegliches Ziel

Diese Hypothese zu widerlegen, war besonders schwierig. Ihr vorhergesagter Aufwand hängt von ω ab, und ω ist unbekannt. Ein Algorithmus, der beim heute besten Wert von ω schneller ist als die Hypothese, könnte diesen Vorsprung verlieren, falls jemand später eine schnellere Matrizenmultiplikation fände.

Virginia Vassilevska Williams vom MIT und Or Zamir von der Universität Tel Aviv umgehen das Problem. Sie beweisen, dass sich für jedes hinreichend große k eine k-Clique in etwa n^((ω/3 − c)k) Schritten finden — und sogar zählen — lässt, wobei c eine positive Konstante ist, die weder von k noch von ω abhängt. Die Ersparnis wird am wahren Wert von ω gemessen, wie auch immer er sich herausstellt. Sie bleibt sogar bestehen, wenn ω = 2 ist, der beste denkbare Fall.

Einen Keil falten

Das Herzstück der Methode betrifft Muster aus neun Knoten. Der Standardansatz teilt sie in drei Gruppen zu je drei auf und multipliziert drei riesige Matrizen. Die Autoren betrachten einen Keil (wedge) — zwei Kanten mit einem gemeinsamen Knoten — und fügen zwischen zwei der Matrizen eine Tabelle ein, die nichts verändert: die Einheitsmatrix. Diese schreiben sie dann als Summe einiger weniger „Vertauschungen“ (swaps), von denen jede die beiden Kanten des Keils zu einer verschmilzt, plus einen Rest von niedrigem Rang.

Die Vertauschungen ergeben einfachere Muster mit weniger Kanten, die wiederum mit derselben Methode behandelt werden; ein Muster aus neun Knoten hat höchstens 36 Kanten, also endet die Rekursion. Der Rest von niedrigem Rang verkleinert die zu multiplizierenden Matrizen. Erst die Anwendung des Tricks auf zwei getrennte Keile zugleich bewahrt einen Gewinn selbst bei ω = 2. Jedes k, das ein Vielfaches von neun ist, lässt sich dann in neun Blöcke gruppieren.

Real, aber winzig

Die Autoren geben keine Zahlen für den Gewinn an. Sie beschreiben die Konstanten als irgendwo „zwischen verschwindend gering ohne Optimierung und winzig mit erheblichen Optimierungen“. Es geht nicht um Geschwindigkeit in der Praxis, sondern darum, dass eine Schranke, an die man jahrzehntelang glaubte, nicht existiert.

Die Folgen reichen über Cliquen hinaus. Exakte Algorithmen für schwere Optimierungsprobleme wie Max-Cut und Max-2-SAT, die für n Variablen etwa 2^(ωn/3) Schritte brauchten, erhalten nun ebenfalls einen kleineren Exponenten. Dasselbe gilt für das Zählen von Kopien eines beliebigen festen kleinen Graphen.

Was die KI beitrug

In einem eigenen Abschnitt beschreiben die Autoren, wie sie mit ChatGPT-6 gearbeitet haben, das sie über die öffentliche Weboberfläche nutzten. Ausgehend von ihren eigenen Ideen für Cliquen aus fünf Personen und von einem neueren Ergebnis von OpenAI, das eine andere Vermutung widerlegt, die Exponentialzeit-Hypothese (Exponential Time Hypothesis), fand das Modell eine erste, komplizierte Verbesserung für 5-Cliquen. Die Autoren destillierten sie dann, mit Hilfe der KI, zu der algebraischen Zerlegung im Kern des Beweises, die sie als „fast ausschließlich den Beitrag der KI“ ansehen. Das algorithmische Gerüst, das darum herum gebaut ist, stammt nach ihren Worten hauptsächlich von ihnen.

Eine Bemerkung sticht hervor. Von KI erzeugte undurchsichtige Beweise seien für Menschen schwer zu lesen, merken die Autoren an — und sie „waren beeindruckt, dass sie auch für die KI selbst schwer zu verstehen sind“.