ZAHLEN AUSWÄHLEN, DIE AUFGEHEN – FAST SO SCHNELL, WIE MAN SIE LIEST

Hier ein Rätsel, das jeder formulieren kann. Sie haben eine Liste ganzer Zahlen – etwa 3, 9, 14, 20 – und ein Ziel, etwa 23. Können Sie einige davon so auswählen, dass sie zusammen genau das Ziel ergeben? (Hier ja: 3 + 20 oder 9 + 14.) Das ist Subset Sum (Teilsummenproblem), eines der grundlegendsten Probleme der Informatik. Die Arbeit beschreibt es als grundlegendes NP-vollständiges Problem, aus einer Familie von Problemen, die dafür bekannt sind, exakt schwer lösbar zu sein.

Es gibt allerdings ein Schlupfloch. Sind die Zahlen nicht zu groß, laufen geschickte Algorithmen in einer Zeit, die von ihrer Größe abhängt. Die klassische Methode von Bellman aus dem Jahr 1957 braucht eine Zeit proportional zur Anzahl der Zahlen n mal dem Ziel t. Seitdem wurden die Algorithmen immer besser:

• Pisinger (1999): proportional zu n × N, wobei N die größte Zahl ist;
• Bringmann (2017): ungefähr n + t;
• mehrere Teams (2021–2024): ungefähr n + N^(5/3), dann n + N^(3/2).

Der heilige Gral war eine Laufzeit von ungefähr n + N – kaum mehr, als die Eingabe zu lesen. Forscher des Gebiets hatten es „das wichtigste offene Problem“ dieser Forschungslinie genannt.

Haarscharf am Ziel

Lin Chen, Yuchen Mao und Guochuan Zhang von der Zhejiang-Universität in China legen einen Algorithmus vor, der in der Zeit n + N^(1+ε) läuft, wobei ε jede im Voraus festgelegte kleine positive Zahl sein kann – 0,1, 0,01, 0,001. Er ist deterministisch, akzeptiert negative Zahlen und wiederholte Werte und wird von einem mathematischen Beweis begleitet. Die Autoren nennen diese Laufzeit nahezu optimal.

Das Ergebnis lässt sich auf Vektoren übertragen: Elemente so auszuwählen, dass mehrere Summen gleichzeitig ihre Ziele treffen, mit einer Zeit von N^(d+ε) für d Koordinaten. Das wiederum beantwortet einen Teil einer Frage mehrerer Gruppen zur ganzzahligen Programmierung – dem Finden ganzzahliger Lösungen von Gleichungssystemen mit beschränkten Variablen. Zwei Folgerungen werden explizit ausgearbeitet: eine Zahlenmenge in zwei gleiche Hälften aufzuteilen und Aufgaben so gleichmäßig wie möglich auf zwei identische Maschinen zu verteilen.

Zahlen in eine höhere Dimension heben

Die Schlüsselidee ist geometrisch. Man wusste bereits, dass das Problem leicht ist, wenn die Zahlen dicht liegen und das Ziel tief im Bereich der möglichen Summen liegt. Die Beobachtung der Autoren: Eine dünn besetzte Zahlenmenge kann dicht aussehen, wenn man sie in einer höheren Dimension betrachtet.

Ihr Beispiel ist die Menge {11, 12, 22, 24}. Man schreibe 11 und 22 als einen und zwei Schritte entlang einer ersten Achse, und 12 und 24 als einen und zwei Schritte entlang einer zweiten Achse. Die möglichen Summen füllen dann jeden Punkt eines kleinen Quadrats von 4 mal 4. Drückt man dieses Quadrat aber wieder auf eine Linie zusammen – indem man 11x + 12y berechnet –, bilden die Summen sieben getrennte Gruppen mit Lücken dazwischen, verstreut zwischen 0 und 69. Die Lücken sind eine Täuschung der Projektion; in zwei Dimensionen ist die Struktur einfach.

Der Algorithmus baut solche höherdimensionalen Koordinaten für jede beliebige Eingabe auf, gestützt auf Ergebnisse der additiven Kombinatorik. Innerhalb des „gefüllten“ Bereichs gibt es die Antworten umsonst. Nur eine schmale Zone nahe dem Rand erfordert echte Arbeit, die der Algorithmus in kleinere Probleme zerlegt und rekursiv löst. Jede Runde verkleinert diese Zone stark, und es kommt immer nur eine konstante Zahl neuer Dimensionen hinzu.

Wie der Beweis entstand

Die Arbeit beginnt mit einem „KI-Hinweis“. Die Autoren entwarfen den Hauptweg des Beweises selbst, aufbauend auf ihren eigenen jüngeren Arbeiten zu dichten, mehrdimensionalen Varianten des Problems. Dann nutzten sie ein KI-Modell, GPT Astra Ultra, um diese Ideen in vollständige mathematische Beweise zu verwandeln. Es blieb an mehreren Lemmata hängen, die mit Ideen der Autoren gelöst wurden; eine öffentliche Forschungsnotiz dokumentiert die Gespräche. Sobald der grundlegende randomisierte Algorithmus fertig war, erweiterte das Modell ihn auf die deterministischen und mehrdimensionalen Varianten „ohne jede Anleitung durch die Autoren“. Das Modell entwarf auch die Arbeit und überprüfte, so schreiben die Autoren, ihre Hauptergebnisse mit einem Beweis im Beweisassistenten Lean 4. Die Autoren übernehmen die volle Verantwortung für den Inhalt.

Noch nicht ganz die Ziellinie

Der Exponent ist 1 + ε statt genau 1, und die versteckten Konstanten wachsen, wenn ε schrumpft; die Abhängigkeit von der Zahl der Dimensionen ist nicht optimiert. Die Autoren selbst beschreiben den Algorithmus als „ziemlich verwickelt“. Die Arbeit ist theoretisch: Sie berichtet weder eine Implementierung noch Leistungstests.