[Перевод] Две лаборатории против одной гипотезы: что происходит вокруг ETH

OpenAI и Anthropic сообщили, что их исследовательские модели нашли алгоритмы, опровергающие гипотезу экспоненциального времени — ETH. На этом предположении построены многочисленные оценки сложности вычислительных задач. Если результат выдержит проверку, исследователям придётся пересмотреть часть представлений о том, какие алгоритмы вообще возможны.

Масштаб последствий зависит от того, какое ускорение обещают новые алгоритмы. Для этого нужно разобраться в связи ETH с проблемой P против NP.

Что опубликовали лаборатории

26 октября 2026 года OpenAI объявила о результатах в трёх областях: математическом анализе, теории вычислительной сложности и квантовой теории поля. Заявление об ETH относится ко второй. Компания выложила текст доказательства и его формализацию в Lean — системе проверки математических доказательств.