Anthropic опубликовала алгоритм Claude для 3-SAT с заявкой на опровержение ETH

Anthropic опубликовала исследовательский артефакт, в котором основное открытие приписывает внутренней модели Claude: детерминированный алгоритм для 3-SAT с заявленным временем 2^o(n). В работе также сказано, что метод распространяется на подсчёт решений для #3-SAT, а при корректности результата это означало бы опровержение гипотезы экспоненциального времени, ETH.

Компания подчёркивает, что это исследовательский результат, а не практический прорыв для продовых SAT-задач. Публикация включает препринт и формализацию в Lean 4, но заявленный выигрыш относится к асимптотике и, по словам авторов, не ускоряет решение реальных формул на практике.

Отдельный нюанс для тех, кто смотрит на это как на AI workflow: проверить сам артефакт можно по опубликованным материалам, а воспроизвести путь к нему — пока нет. Anthropic пишет, что ключевой алгоритм нашла внутренняя исследовательская версия Claude после 14 млн выходных токенов без участия человека, но параметры модели и конфигурация запуска публично не раскрыты.