Un paper afirma haber refutado la ETH con una prueba simplificada
A simplified proof of ETH is False [pdf]
Shiva Kintali presenta una exposición simplificada de la prueba de OpenAI que refuta la Hipótesis del Tiempo Exponencial: para todo ε > 0 fijo, ofrece un algoritmo determinista para 3-SAT que corre en Cε(n + m + 1)^cε · 2^(εn) operaciones de bits. La construcción combina esparsificación, acotación de ocurrencias, reemplazo espectral e interpolación racional, y solo invoca sin demostrar el lema de esparsificación. Si es correcta, contradice la formulación estándar de la ETH tomando ε = δ/2.
El único resultado sobre la complejidad de SAT que invocamos sin demostración es el lema de esparsificación enunciado a continuación.