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 2^{O(\sqrt{n\log n})} für Graphen mit n Ecken gefunden und mehr als 30 Jahre später gelang Babai dann Ende 2015 ein Durchbruch mit einem Algorithmus in quasi-polynomieller Zeit, d.h. Laufzeit 2^{O((\log n)^c)} für eine Konstante c.

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)

  1. #1 hubert taber
    16. Januar 2017

    P kann nicht gleich NP sein.
    da es meiner meinung nach kein NP gibt.
    es gibt keine nichtdeterministische turingmaschine.

    hier wird vermutlich ein problem konstuiert das in wahrheit nicht existiert.

    mfg. hubert taber

  2. #2 user unknown
    https://demystifikation.wordpress.com/2017/01/11/wordpress-blogchart/
    16. Januar 2017

    Vielleicht sollte man dazu sagen, dass das Video erst nach ca. 11 Minuten losgeht. Es startet nämlich mit dem Text “livestream starting” so dass man meinen kann, da nichts passiert, dass es vorbei ist und nur ein Defaultbild zeigt.
    Leider ist es auf französisch, eine schöne Sprache, aber man versteht sie nicht. 🙂

  3. #3 hubert taber
    17. Januar 2017

    nach meinem verständnis gibt es nur 2 komplexitätsklassen:
    P und EXP.
    nicht NP.
    vermutlich durch zulange eingabezeilen die möglicherweise auch noch falsch sind ergibt sich scheinbar NP.
    mfg. hubert taber.

  4. #5 hubert taber
    21. Januar 2017

    noch eine bemerkung zur zahlentheorie:
    ich kenne ein zahlensystem mit nur einer stelle.
    ohne kommastellen.
    durch die addition von null-dimensionalen punkten ist stufenloses rechnen möglich.
    ohne limes, ohne näherungsfehler, hochgenau und gestochen scharf.

    auch n mal unendlich ist möglich.

    das system ist also mehr als vollständig lieber kurt gödel.
    und dein dümmliches unvollständigkeits-theorem wurde von noch dümmeren zum mathematischen satz scheinbewiesen.

    mfg. hubert taber

  5. #6 hubert taber
    21. Januar 2017

    auch der scheinbare widerspruch im system ist nur mutwillig konstruiert.
    es gibt kein paradoxon.

    ein paradoxon ist nur als wirres, widersprüchliches und scheinlogisches wortspiel möglich.

    mfg. hubert taber