OpenAI заявила, что ИИ вывел алгоритм, опровергающий гипотезу об экспоненциальном времени

OpenAI объявила 26 октября, что её ИИ создал детерминированный алгоритм точного подсчёта решений CNF-формул фиксированной ширины за субэкспоненциальное время, что опровергло бы гипотезу об экспоненциальном времени (ETH). Материалы с Lean-формализациями опубликованы, проверку организуют Рассел Импальяццо, Рамамохан Патури и Райан Уильямс; также заявлены результаты по локальному сглаживанию волн и построению квантовых теорий поля.

• Алгоритм считает решения CNF-формул фиксированной ширины за субэкспоненциальное время
• Для формул с ≤3 литералами в клаузе это опровергло бы ETH
• Проверку координируют Импальяццо, Патури и Уильямс, но не сертифицируют заявку
• Отдельно заявлены результаты по локальному сглаживанию и теории Янга — Миллса