Mit dem Namen “Bourbaki” verbinden Mathematiker vor allem die bekannte Lehrbuch-Reihe, von der übrigens vor einigen Monaten nach 33-jähriger Unterbrechung wieder ein neuer Band erschienen ist. Daneben gibt es aber noch das “Séminaire Bourbaki”, wo viermal im Jahr einen Tag lang Vorträge über die jeweils angesagtesten neueren mathematischen Entdeckungen gehalten werden, und zwar nicht von den jeweiligen Entdeckern, sondern von “Unbeteiligten”, die sich in die Beweise einarbeiten und dann auch einen Überblick über den Beweis veröffentlichen sollen.
Einem Professor meines Instituts passierte es mal, dass er im Séminaire Bourbaki über ein spektakuläres neues Resultat seines früheren Doktorvaters vortragen sollte, dann aber bei der Ausarbeitung des Überblicksartikels einen nicht-korrigierbaren Fehler in der Arbeit fand, über die er hatte berichten sollen, womit dann nicht nur jenes Resultat sondern auch sein eigener Bourbaki-Vortrag hinfällig war, denn natürlich wollte man keinen Vortrag über ein fehlerhaftes Resultat haben. (Er durfte dann aber ein Jahr später über einen Beweis eines anderen Satzes vortragen.)
Etwas ähnliches scheint sich in den letzten Wochen vor dem Bourbaki-Seminar dieses Wochenendes zugetragen zu haben, wenn auch mit anderem Ausgang.
Einer der angekündigten Vorträge war über ein Problem der Komplexitätstheorie, nämlich das Graphenisomorphismusproblem: wie schnell lässt sich algorithmisch entscheiden, ob zwei Graphen isomorph sind. Es ist nicht bekannt, ob man dies in polynomieller Zeit entscheiden kann oder ob das Problem vielleicht NP-vollständig ist. Laszlo Babai und Eugene Luks hatten Anfang der 80er Jahre Algorithmen mit einer Laufzeit 
Babais Arbeit gilt als “the theoretical computer science result of the decade” und war demzufolge nun für dieses Wochenende eines der Themen im Séminaire Bourbaki, und die Geschichte wiederholte sich insoweit, dass der Vortragende Harald Helfgott in seiner Vorbereitung einen Fehler in Babais Beweis fand. Zumindest führte das in diesem Fall nicht zur Annulierung des Vortrags, denn Babais Algorithmus lief jedenfalls in subexponentieller, wenn auch nicht quasi-polynomieller Zeit, und das war immer noch interessant genug für einen Bourbaki-Vortrag.
Ganze 5 Tage vor dem Seminar gelang es Babai dann aber doch noch, den Algorithmus so zu modifizieren, dass er in quasi-polynomieller Zeit läuft und laut Helfgott ist der neue Algorithmus und Beweis nun auch tatsächlich korrekt.
Helfgotts Vortrag ist inzwischen auchauf YouTube:
Bekanntlich ist das P=NP-Problem der heilige Gral der Komplexitätstheorie und anders als bei vielen anderen offenen mathematischen Problemen gehen hier die Meinungen weit auseinander, was man als Ergebnis erwarten sollte, ob P=NP oder nicht. Babais Resultat kann man wohl als Indiz in Richtung P=NP ansehen: ein bisher für NP-schwer gehaltenes Problem lässt sich nun doch in quasi-polynomieller Zeit lösen, was nicht mehr sehr weit von polynomieller Zeit entfernt ist.
Für praktische Zwecke verwendet man übrigens andere Algorithmen, die für eingeschränkte Klassen von Graphen schnellere Lösungen liefern.
Kommentare (6)