Habr: заявления об опровержении ETH не доказывают взлом криптосистем

Как подчёркивает Habr, из заявлений о 3-SAT пока не следует, что существующие криптосистемы взломаны. Чтобы сделать такой вывод, нужен конкретный способ атаки, оценка его затрат и применимость к используемым параметрам криптосистемы. Даже подтверждение математического результата само по себе не заменяет ни одного из этих условий.

Субэкспоненциальный алгоритм для 3-SAT, о котором, по сообщению Habr, заявляет Anthropic, может опровергнуть гипотезу экспоненциального времени — ETH. Но даже корректный результат такого рода не решает автоматически проблему P против NP: время работы алгоритма всё ещё может превышать любой полином. Это существенная граница заявленного достижения.

Что сообщили лаборатории

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

Anthropic, согласно той же публикации, приписывает своей внутренней модели Claude алгоритм, который решает задачу 3-SAT за субэкспоненциальное время. Заявленный алгоритм также должен подсчитывать число удовлетворяющих формуле наборов значений. Речь здесь именно о заявлении компании, а не об установленной корректности алгоритма.

Какую границу проверяет ETH

В изложении Habr гипотеза утверждает, что для 3-SAT нет алгоритма со временем работы 2^(o(n)), если не учитывать полиномиальные множители по размеру входа. Поэтому заявленный Anthropic результат, если он подтвердится, противоречил бы ETH.

Однако опровержение этой гипотезы и доказательство равенства P = NP — разные результаты. Субэкспоненциальный алгоритм может оставаться сверхполиномиальным. Из слова «субэкспоненциальный» нельзя заключить, что задача получила полиномиальное решение: именно эту оговорку подчёркивает публикация.

Что означает внешняя проверка

Habr отдельно указывает, что участие Райана Уильямса, Рассела Импальяццо и Рамамохана Патури во внешнем изучении результата OpenAI не означает научного подтверждения опровержения ETH. Само участие исследователей в проверке нельзя считать её положительным итогом.