Matching beschreibt eines der grundlegendsten Probleme der Informatik: Wie ordnet man Elemente zweier Mengen einander optimal zu? Kann jede Person einer Reisegruppe einen Platz in einem Bus einnehmen oder jeder Jobbewerber eine Stelle? »Matching ist eine der ergiebigsten Ideenquellen für neue Erkenntnisse in der Mathematik, der Informatik und anderen Bereichen«, erklärte der Mathematiker Gil Kalai von der Hebräischen Universität in Jerusalem in seinem Blog.

Für solche Zuordnungen – und deutlich kompliziertere Varianten – gibt es effiziente Algorithmen. Doch eine grundlegende Frage blieb offen: Wie effizient können die besten Algorithmen im Prinzip überhaupt sein? »Dieses Problem gilt seit Langem als der ›Heilige Gral‹ der Komplexitätstheorie«, so Kalai. Und nun hat ein Team um Thomas Thierauf von der Hochschule Aalen in einer noch nicht begutachteten Arbeit eine Antwort darauf vorgestellt.

Vom Dating zum Algorithmus

Das Team um Thierauf sah sich hierfür den Spezialfall des bipartiten Matchings an, also einer Paarung: Jedem Element der einen Menge soll eines der zweiten Menge zugeordnet werden. Ein beliebtes Beispiel dafür ist das »Heiratsproblem«, bei dem man eine Gruppe von Singles miteinander verkuppelt. Die Schwierigkeit besteht allerdings darin, dass jedes Individuum dabei seine eigenen Vorlieben mitbringt und vielleicht mehrere Personen mit dem gleichen Partner zusammensein möchten. Die Aufgabe besteht darin, für jeden Single einen bereitwilligen Partner zu finden.

Ein Matching-Algorithmus muss also zunächst einmal prüfen, ob das Problem lösbar ist, und anschließend eine passende Verteilung finden. Eine solche Lösung für den bipartiten Fall zu finden, ist nicht allzu schwierig. Die Frage, die sich Informatikerinnen und Informatiker aber stellen, ist: Wie schnell kann so ein Algorithmus sein?

Natürlich hängt die Laufzeit eines Programms vom spezifischen Problem ab. Doch in der theoretischen Informatik gibt es das Gebiet der Komplexitätstheorie, bei der stets das Worst-Case-Szenario angenommen wird: Wie lange braucht ein Algorithmus maximal, um ein Problem der Größe N zu lösen? Im geschilderten Fall des Heiratsproblems entspricht N der Anzahl an zu verkuppelnden Personen. Und wie sich herausstellte, wächst die Anzahl der Rechenschritte – und damit auch die Laufzeit – des naheliegenden Lösungsalgorithmus linear mit N an. Fachleute vermuteten aber, dass es auch schneller gehen könnte. Insbesondere, wenn es gelingt, das Problem zu parallelisieren.

Im Jahr 1980 zeigte sich, dass diese Vermutung zutraf: Es gibt Algorithmen, die solche bipartiten Matching-Probleme in logarithmischer Zeit aus parallelen Prozessoren lösen (die Anzahl der Schritte ist dann proportional zum Logarithmus von N). Allerdings funktionieren sie nur mithilfe zufälliger Ereignisse. Damit gehört das Verfahren zur Komplexitätsklasse RNC. 

• P-Probleme
  P-Probleme sind vergleichsweise einfach zu lösen: Der Rechenaufwand steigt nur langsam mit der Größe des Problems an. Möchte man zum Beispiel zwei Zahlen miteinander multiplizieren, kann das bei sehr großen Zahlen zwar aufwendig erscheinen – aber ein Computer kann das stets bewältigen, egal wie riesig die Zahlen sind.
• NP-Probleme
  Bei NP-Problemen ist das hingegen anders. Diese können für einfache Spezialfälle vielleicht noch gelöst werden, doch es gibt keine effiziente Methode, um allgemeine Aufgaben dieser Art zu berechnen. Ein typisches NP-Problem besteht darin, zu einer vorgegebenen Zahl die Primteiler zu bestimmen: jene Primzahlen, die miteinander multipliziert die ursprüngliche Zahl ergeben. Für einfache Beispiele wie 15 lassen sich die Primteiler (3 und 5) schnell ermitteln. Doch wenn man die Primteiler einer 1000-stelligen Zahl berechnen möchte, sind Computer schnell überfordert. NP-Probleme zeichnen sich aber auch dadurch aus, dass sich ihre Lösung einfach überprüfen lässt. Falls mir jemand eine 1000-stellige Zahl und ihre vermeintlichen Primteiler vorgibt, kann ich die Primzahlen miteinander multiplizieren (das ist ja aus mathematischer Sicht einfach, weil es ein P-Problem ist) und sofort sehen, ob das Ergebnis mit der 1000-stelligen Zahl übereinstimmt.

Die Rolle des Zufalls

In der Praxis ist diese Einschränkung kein Problem. Für viele Anwendungen reicht es völlig aus, zufällige Bits durch Pseudozufallszahlen zu ersetzen. Doch theoretisch bleibt eine zentrale Frage offen: Ist der Zufall wirklich notwendig, oder geht es auch deterministisch?

Fachleute suchten jahrzehntelang nach einer Lösung des bipartiten Matchings in logarithmischer Zeit, ohne auf zufällige Werte angewiesen zu sein. Und genau das scheint nun den Forschern um Thierauf gelungen zu sein. Falls sich das Resultat bestätigt, würde das Problem in die Komplexitätsklasse »NC« fallen (kurz für »Nick’s Class«, nach dem Informatiker Nick Pippenger).

NC umfasst alle Probleme, die sich auf einem Parallelrechner in deutlich besserer Zeit als auf einer sequenziell arbeitenden Maschine lösen lassen. »Falls korrekt, löst die Arbeit ein zentrales Problem bei Parallelalgorithmen und der Derandomisierung, das seit den 1980er-Jahren ungelöst war«, schreibt der Mathematiker Scott Aaronson von der University of Texas in Austin in seinem Blog. Zudem vertieft sie auch das Verständnis darüber, wie viel Zufall effiziente Algorithmen tatsächlich brauchen.