Математик опубликовал упрощённое доказательство ложности ETH
A simplified proof of ETH is False [pdf]
Шива Кинтали представил 22-страничную работу, в которой для любого фиксированного ε > 0 строится детерминированный алгоритм решения 3-SAT за Cε(n + m + 1)^cε · 2^(εn) битовых операций. Это опровергает гипотезу об экспоненциальном времени (ETH). Доказательство упрощает подход OpenAI и сочетает разреживание, ограничение вхождений, спектральную замену и рациональную интерполяцию.
Для любого фиксированного ε > 0 мы даём детерминированный алгоритм для 3-SAT на n переменных и m дизъюнктах, использующий Cε(n + m + 1)^cε · 2^(εn) битовых операций, что опровергает ETH.