Mathematiker hält bahnbrechenden o(n log n)-Multiplikationsalgorithmus für plausibel
The recently proposed o(n log n) integer multiplication algorithm [pdf]
David Harvey von der UNSW Sydney kommentiert einen kürzlich veröffentlichten Algorithmus zur Multiplikation n-Bit-Integer, der eine Komplexität von o(n log n) Bitoperationen beansprucht – eine Verbesserung gegenüber der bisher als optimal geltenden Schranke O(n log n). Harvey hat die Details nicht vollständig geprüft, hält die Behauptung aber für plausibel, nachdem er sich den Beweis mit einem LLM erklären ließ. Er diskutiert die Konsequenzen für die mathematische Forschung und die Rolle von KI.
Die Tatsache ist, dass es jetzt ein automatisiertes System gibt, das mathematische Forschung betreiben kann – zumindest den Teil, der das „Lösen harter Probleme“ umfasst –, weit besser als jeder Mensch.
- jdb1729
> Es wäre gut, einen formalisierten Beweis des o(n log n)-Ergebnisses zu haben, zum Beispiel in Lean. Soweit ich das beurteilen kann, existiert noch keiner.
Das Ergebnis ist vollständig in Lean von @platypii und mir formalisiert (auf Mathlibs TM2-Maschine), mit laufenden Verbesserungen am Exponenten (derzeit bei 1-2^-14.38): https://github.com/platypii/integer-mult-bounds-lean
Beiträge sind willkommen!
- Kapura
> Ich habe das Paper nicht tatsächlich gelesen. Tatsächlich gibt es drei eng verwandte Paper [TC26a], [TC26b], [TC26c], und ich habe keines davon gelesen. Ich habe es versucht, aber bald aufgegeben. Der Mathe-Dump scheint nicht stark in der Darstellung zu sein. Stattdessen habe ich Fable gebeten, mir [TC26a] zu erklären. Fable scheint das Argument zu verstehen und hält es für korrekt.
das fühlt sich nicht wie ein gesunder Ort an
- kenferry
> Es gibt einen weiteren Aspekt der Situation, den ich betonen möchte. Nach zwei Wochen sehr harter Arbeit habe ich es geschafft, nur einen kleinen Bruchteil von [TC26a] zu verstehen. Wenn ich Fable nach dem Paper frage, scheint es das Ganze in nur wenigen Minuten zu lesen und zu verstehen, selbst wenn es mit einem frischen Kontext beginnt. Ich weiß, dass einige Leser mit meiner anthropomorphen Terminologie unwohl sein könnten, aber ich glaube, dass „verstehen“ zutreffend ist, in dem Sinne, dass das LLM scheinbar in der Lage ist, alle Arten von Fragen zum Paper korrekt und klar zu beantworten, einschließlich einiger sehr kniffliger technischer Details. Genau so würde ich sagen, dass ein menschlicher Kollege etwas „verstanden“ hat. Diese Kluft zwischen menschlicher und LLM-„Gedankengeschwindigkeit“ ist gelinde gesagt beunruhigend.
Das ist sehr seltsam, weil es überhaupt nicht meiner Erfahrung mit diesen Systemen entspricht. Ja, sie KLINGEN im Allgemeinen selbstbewusst, aber Code (sagen wir), der für mich schwer zu verstehen ist, ist normalerweise auch für die Maschine schwer zu verstehen, und obwohl sie unermüdlicher ist als ich, ist sie nicht klüger.
Dieser Mathematiker ist in einer sehr guten Position, um zu beurteilen, ob Fable es versteht oder nicht, aber es ist seltsam und widerspricht meiner Erfahrung.
- jdb1729
> Das neue Ergebnis impliziert nicht direkt neue Komplexitätsschranken für Polynommultiplikation über einem festen endlichen Körper, sagen wir Multiplikation in F2[x]. Der Stand der Technik für dieses Problem ist ein Algorithmus, der Polynome vom Grad n in Zeit O(n log n 4^log*(n)) multipliziert [HvdH19].
@platypii und ich haben einen Lean-Beweis derselben Verbesserung für DFT über endlichen Körpern primer Ordnung erhalten (was Polynommultiplikation über den Faltungssatz ergibt): https://github.com/platypii/integer-mult-bounds-lean/blob/ma...
- flebron
Beachte, dass in diesem Fall der Titel „O(n log n)“ sagt, aber der wichtige Teil ist, dass dies „o(n log n)“ ist, nicht nur „O(n log n)“. Ersteres ist eine echte Teilmenge des Letzteren. Wir wussten bereits, wie man zwei n-Bit-Ganzzahlen in O(n log n)-Zeit multipliziert, mittels FFT.
- CH-Abhinav
Neu hier, aber wie hilft das allgemein? Meistens verwenden wir GEMM statt Strassen, obwohl die Zeitkomplexität geringer ist. Frag einfach, keine Ahnung :)
- kleiba2
Interessant, dass KI offenbar keine Papers für Menschen schreibt: Selbst Experten haben Mühe, sie zu verstehen. Aber andere KIs tun es. Also schreibt KI im Grunde Papers für andere KIs.
- yaoke259
Toller Artikel und Einführung von einem fellow Sydney-sider, hat mich gefesselt! Als jemand, der kein Mathe-Genie ist, sind die technischen Details an mir vorbeigeflogen, aber die Prosa, die es mir ermöglichte, mich tief in die Lage der Leute in diesem Feld einzufühlen, war sehr erhellend. Mir war nie klar, wie groß die Sache mit dem Mathe-Dump war und wie sehr er das Feld erschüttert hat. Ich schätze, wir versuchen alle gemeinsam, dieses ganze Ding von „Intelligenz auf Knopfdruck“ zu verstehen.