r/informatik • u/giraffenkaraffe • 23h ago
Nachrichten Die Exponential Time Hypothesis wurde scheinbar widerlegt
OpenAI haben in ihrem math Repo ein Preprint veröffentlicht, in dem ein Algorithmus beschrieben wird, der laut ihnen die in der Exponential Time Hypothesis postulierte Laufzeitschranke brechen soll. Welche Techniken im Algo angewandt werden, habe ich beim sehr oberflächlichen querlesen nicht verstanden. Lediglich, dass der Algorithmus eine Reduktion des Entscheidungsproblems auf ein Zählproblem über Polynomen beinhaltet, was in der Literatur in der Sparte m.E. keine ungewöhnlichen Kunstgriffe sind.
Absolut verrückt, was zur Zeit passiert. Es hat zwar keine krassen Auswirkungen bzgl. P vs. NP, ist aber nichtsdestotrotz beeindruckend.
Ich bin gespannt darauf, ob das Ergebnis bestätigt wird und ob irgendwelche der verwendeten Techniken in andere Teilgebiete der Komplexitätstheorie einfließen werden.