🧪 Модель Claude опровергла гипотезу экспоненциального времени
Anthropic опубликовала препринт «A 2^o(n) Time Algorithm for 3-SAT»: 16 октября 2026 её модель нашла детерминированный алгоритм, решающий 3-SAT и #3-SAT за 2^O(n log log n / sqrt(log n)) — субэкспоненциально, что опровергает ETH. Доказательство в Lean 4 машинно проверено; человек проверил его лишь частично.
🌍 Если результат подтвердится, ETH и SETH ложны: сотни работ по сложности вычислений придётся перепроверять. Ядро алгоритма найдено без человеческих подсказок — 14 млн токенов.
👤 Теоретикам: границы, выведенные из ETH, требуют ревизии. Всем остальным — пример того, как LLM становятся инструментом математических открытий, хотя выигрыш появляется лишь при ~10^10000 переменных.
Источник 1: https://hexagonmath.org/2610.00577v1 Источник 2: https://github.com/anthropics/formal-math/tree/16a5ce41304fcdaea4e0be7c132e1c361dc26da5/eth