Shiva Kintali will ETH mit einem vereinfachten Beweis widerlegt haben
A simplified proof of ETH is False [pdf]
Der Autor präsentiert einen deterministischen 3-SAT-Algorithmus, der für jedes feste ε > 0 in Cε(n + m + 1)^cε · 2^εn Bitoperationen läuft – und damit die Exponential Time Hypothesis widerlegt. Der Beweis vereinfacht eine frühere Argumentation von OpenAI und kombiniert Sparsification, beschränkte Variablenvorkommen, spektrale Ersetzung und rationale Interpolation. Kern ist eine Deformation der Klauseln, deren Auswertung an ganzzahligen Stützstellen per Taylor-Entwicklung und Interpolation den Lösungscount exakt rekonstruiert.
Für jedes feste ε > 0 geben wir einen deterministischen 3-SAT-Algorithmus auf n Variablen und m Klauseln an, der Cε(n + m + 1)^cε · 2^εn Bitoperationen benötigt und damit ETH widerlegt.