Ben Recht analysiert in seinem Artikel vom Oktober 2026 die von OpenAI veröffentlichten mathematischen Preprints zur Beschleunigung der Fast Fourier Transformation (FFT). Er kritisiert, dass der angebliche Durchbruch in Wirklichkeit ein theoretischer Ausnutzungseffekt („Exploit“) ungenauer Berechnungsmodelle ist, die gigantische („galaktische“) Konstanten und unendliche Rechenpräzision voraussetzen. Die Algorithmen entbehren jeglicher praktischer Relevanz für reale Computersysteme und spiegeln eine bedenkliche Entkoppelung theoretischer Informatik von realer Hardware wider.
Wichtigste Punkte
Traditionelle Komplexität: Der klassische Cooley-Tukey-Algorithmus berechnet die diskrete Fouriertransformation (DFT) in weniger als $5n \log_2 n$ Rechenschritten.
Galaktische Konstanten: OpenAIs FFT-Algorithmus nutzt Big-O-Notationen mit gigantischen versteckten Konstanten (geschätzt $C \approx 10^{100}$ bei $n = 10^{12}$), wodurch der klassische Algorithmus für alle praxisrelevanten Eingabegrößen $n$ drastisch schneller bleibt.
Irreales Berechnungsmodell: Das theoretische Modell setzt exakte komplexe Arithmetik mit beliebiger Präzision voraus und erfordert die Multiplikation komplexer Zahlen, deren Beträge superpolynomisch mit $n$ wachsen.
Widerspruch zu historischen Beweisen: Das Ergebnis umgeht die strikten Einschränkungen von Jacques Morgensterns Beweis aus dem Jahr 1973 (welcher beschränkte Beträge forderte) und ignoriert unlösbare numerische Instabilitäten.
Matrixmultiplikation: Ähnliche Probleme zeigen sich in OpenAIs begleitendem Matrixmultiplikations-Paper, das eine asymptotische Laufzeit von $O(n^{2.25})$ behauptet, ohne die darin verborgenen Konstanten quantifizieren zu können.
Diskussions-Highlights
Wert der theoretischen Informatik: Kommentatoren streiten intensiv darüber, ob theoretische Informatik (TCS) als reine Mathematik unabhängig von praktischen Anwendungen existieren darf oder ob unrealistische Berechnungsmodelle wertlos sind.
Vergleich mit Teleskopen: Mehrere Diskussionsteilnehmer verweisen auf den berühmten Ausspruch von Edsger W. Dijkstra, dass die Informatik so wenig etwas mit Computern zu tun hat wie die Astronomie mit Teleskopen.
Nutzen galaktischer Algorithmen: Befürworter argumentieren, dass asymptotische Verbesserungen (selbst mit galaktischen Konstanten) wertvoll sind, um zu beweisen, dass bestimmte theoretische Schranken überwindbar sind, was wiederum Folgeforschung anstößt.
Kritik am KI-getriebenen Output: Die plötzliche Veröffentlichung großer Mengen theoretischen Materials durch OpenAI verdeutlicht, wie automatisierte Systeme formale Schlupflöcher und unpräzise Definitionen in Publikationen maximieren.
Externe Ressourcen & Repositories: Diskutiert werden unter anderem der Harvey–van der Hoeven-Algorithmus (2019) für Integer-Multiplikation in $O(n \log n)$, das GitHub-Repository CrocSwap/integer-mult-bounds zur Optimierung von Ganzzahlmultiplikationen sowie das Konzept der Blum–Shub–Smale-Maschine.
Glossar
Fast Fourier Transform (FFT): Ein hocheffizienter Algorithmus zur Berechnung der diskreten Fouriertransformation (DFT), der Frequenzkomponenten schnell aus digitalen Signalen extrahiert.
Big-O-Notation: Eine mathematische Schreibweise, die das asymptotische Wachstumsverhalten von Algorithmen beschreibt, wobei konstante Faktoren und kleinere Terme vernachlässigt werden.
Galaktische Algorithmen: Algorithmen mit theoretisch optimalem asymptotischem Verhalten, deren versteckte Konstanten so gigantisch sind (oft größer als die Anzahl der Atome im beobachtbaren Universum), dass sie auf realen Computern niemals schneller arbeiten können.
Superpolynomisch: Ein mathematisches Wachstum, das schneller ansteigt als jede polynomiale Funktion (wie $n^2$ oder $n^{10}$).
Diskrete Fouriertransformation (DFT): Eine mathematische Operation, die eine endliche Sequenz von Datenpunkten in ihre Frequenzanteile zerlegt.
Blum–Shub–Smale-Maschine: Ein Berechnungsmodell in der theoretischen Informatik, das Berechnungen über den reellen oder komplexen Zahlen mit exakter Arithmetik anstelle von binären Bits modelliert.
Turing-Maschine: Ein abstraktes mathematisches Modell eines Computers, das Operationen auf einem unendlichen Band ausführt, um prinzipielle Berechenbarkeit und Komplexität zu untersuchen.