Unique Games Conjecture

Die Unique Games Conjecture ist eine unbewiesene Behauptung aus der theoretischen Informatik — also dem Bereich, der untersucht, was Computer prinzipiell können und was nicht. Sie wurde im Jahr 2002 vom Mathematiker Subhash Khot aufgestellt. Im Kern sagt sie: Es gibt eine bestimmte Klasse von Rätseln, die für Computer so schwer zu lösen sind, dass selbst eine ungefähre Lösung praktisch unerreichbar ist. Diese Rätsel heißen « Unique Games » — eine Art Constraint-Satisfaction-Problem, bei dem man Variablen Werte zuweisen muss, sodass möglichst viele Bedingungen gleichzeitig erfüllt sind. Das Besondere an der Vermutung ist nicht das Rätsel selbst, sondern was sie über viele andere Probleme aussagt: Wenn sie stimmt, dann sind ganze Familien von Optimierungsproblemen — also Problemen, bei denen man das bestmögliche Ergebnis sucht — grundsätzlich unlösbar, egal wie clever der Algorithmus ist.

Bedeutung für die Grenzen von Algorithmen

In der Informatik gibt es viele Probleme, für die niemand einen schnellen, exakten Lösungsweg kennt. Dann behilft man sich mit Näherungsalgorithmen: Man findet nicht die perfekte Lösung, aber eine, die nah genug dran ist. Die entscheidende Frage ist: Wie nah kann man kommen?

Genau hier greift die Unique Games Conjecture ein. Sie erlaubt es, für viele solcher Probleme eine untere Schranke zu beweisen — also zu zeigen, dass kein Algorithmus besser als ein bestimmter Schwellenwert abschneiden kann, sofern die Vermutung stimmt. Das klingt negativ, ist aber wertvoll: Man weiß dann, dass der beste bekannte Algorithmus bereits so gut ist, wie es überhaupt geht. Man hört auf, nach etwas Besserem zu suchen, das es gar nicht gibt.

Ein konkretes Beispiel ist das Max-Cut-Problem: Man hat ein Netzwerk aus Knoten und Verbindungen und will es so in zwei Gruppen aufteilen, dass möglichst viele Verbindungen zwischen den Gruppen liegen — nicht innerhalb. Unter der Annahme, dass die Unique Games Conjecture stimmt, ist der sogenannte Goemans-Williamson-Algorithmus aus dem Jahr 1995 bereits optimal. Besser geht es nicht. Ohne die Vermutung ist das offen.

Das Rätsel hinter der Vermutung

Ein Unique-Games-Problem funktioniert so: Es gibt viele Variablen, jede kann einen von k Werten annehmen. Zwischen je zwei Variablen gibt es eine Bedingung der Form « Variable A muss genau um 3 größer sein als Variable B » — also eine eindeutige Zuordnung, daher der Name « Unique ». Ziel ist es, möglichst viele dieser Bedingungen gleichzeitig zu erfüllen.

Die Vermutung behauptet: Selbst wenn fast alle Bedingungen erfüllbar sind, ist es für einen Computer extrem schwer, eine Zuweisung zu finden, die auch nur einen großen Anteil davon erfüllt. Das klingt wie ein enges technisches Detail — ist es aber nicht. Dieses eine Rätsel dient in Beweisen als Ausgangspunkt, um die Schwierigkeit von Dutzenden anderen, ganz verschiedenen Problemen zu erklären.

Man nennt dieses Verfahren eine Reduktion: Man zeigt, dass ein bekanntes schweres Problem in ein neues Problem umgewandelt werden kann. Wenn das gelingt, ist das neue Problem mindestens genauso schwer. Die Unique Games Conjecture funktioniert als eine Art Werkzeugkasten für solche Reduktionen.

Die Unique Games Conjecture in Forschung und Praxis

Die Vermutung ist bis heute weder bewiesen noch widerlegt. Das macht sie zu einem der zentralen offenen Probleme der Komplexitätstheorie — also der Wissenschaft, die untersucht, wie viele Ressourcen ein Computer für ein Problem braucht. Im Jahr 2021 gewann Subhash Khot den Nevanlinna-Preis, eine der höchsten Auszeichnungen in der mathematischen Informatik, unter anderem für diese Vermutung.

In der KI-Forschung taucht die Vermutung auf, wenn es darum geht, wie gut maschinelle Lernverfahren Optimierungsprobleme lösen können. Viele Trainingsaufgaben für neuronale Netze sind solche Optimierungsprobleme. Die theoretische Frage, ob es prinzipiell bessere Näherungen geben kann, ist direkt relevant — auch wenn die Praxis meist mit Heuristiken arbeitet, also Faustregeln, die gut genug funktionieren.

In Tech-Nachrichten begegnet man der Vermutung meistens indirekt: wenn über Durchbrüche in der Komplexitätstheorie berichtet wird oder wenn Forscher zeigen, dass ein bestimmtes KI-Problem grundsätzlich schwer ist. Die Unique Games Conjecture steckt dann oft im Hintergrund — als die Annahme, auf die sich der ganze Beweis stützt.