Informatik löst 40 Jahre altes Matching-Problem

Matching ist 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? Für solche Zuordnungen gibt es bereits effiziente Algorithmen. Doch eine grundlegende Frage blieb offen: Wie effizient können die besten Algorithmen im Prinzip überhaupt sein? Dieses Problem galt seit Langem als der „Heilige Gral“ der Komplexitätstheorie.

Nun hat ein Team um Thomas Thierauf von der Hochschule Aalen in einer noch nicht begutachteten Arbeit eine Antwort darauf vorgestellt. Die Forscher untersuchten den Spezialfall des bipartiten Matchings, 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 darin, dass jedes Individuum eigene Vorlieben mitbringt und vielleicht mehrere Personen mit dem gleichen Partner zusammensein möchten.

Bereits 1980 zeigte sich, dass es Algorithmen gibt, die solche bipartiten Matching-Probleme in logarithmischer Zeit auf parallelen Prozessoren lösen – allerdings nur mithilfe zufälliger Ereignisse. Damit gehört das Verfahren zur Komplexitätsklasse RNC. In der Praxis ist diese Einschränkung oft kein Problem, da man zufällige Bits durch Pseudozufallszahlen ersetzen kann. Doch theoretisch blieb die 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. 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“, benannt 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.

Der Mathematiker Scott Aaronson von der University of Texas in Austin schreibt in seinem Blog: „Falls korrekt, löst die Arbeit ein zentrales Problem bei Parallelalgorithmen und der Derandomisierung, das seit den 1980er-Jahren ungelöst war.“ Zudem vertieft sie das Verständnis darüber, wie viel Zufall effiziente Algorithmen tatsächlich brauchen. Die Arbeit ist noch nicht begutachtet, aber die Fachwelt zeigt sich bereits begeistert.