К содержимому
Дайджест

Безымянная модель OpenAI сломала экспоненциальную гипотезу

Fireship·6 ноября 2026·6:01
можно прочитать что произошло
Открыть на YouTube
Разбор статьи OpenAI о безымянной модели, которая нашла более быстрый алгоритм для задачи 3-SAT и поставила под вопрос ключевую гипотезу теории сложности, — для тех, кто следит за прорывами в computer science.

Что в ролике

Физик OpenAI Дэн Робертс опубликовал 67-страничный PDF, в котором спрятан раздел с утверждением, что безымянная внутренняя модель компании нашла алгоритм для задачи 3-SAT быстрее экспоненты. Раньше гипотеза экспоненциального времени, сформулированная Импальяццо и Патури в 1999 году, служила опорой для более чем 800 работ: она обещала, что 3-SAT и сотни связанных задач нельзя решить принципиально быстрее перебора. Для 3-SAT с n переменными лучшие алгоритмы имели время около 1,3^n, всегда экспоненциальное. Найденный моделью алгоритм работает за примерно 2^(n / sqrt(log n)) — это уже не экспонента, а значит гипотеза ложна. Подход необычен: вместо перебора значений модель свела задачу к подсчёту числа решений, разбила сумму на независимые части и применила интерполяцию Эрмита из XIX века для точного восстановления ответа. Практической пользы пока нет: алгоритм обгоняет перебор только при n больше 10 в степени 10000. Скотт Ааронсон поднял личную оценку вероятности P = NP с 3 до 5 процентов, а авторов гипотезы OpenAI попросила проверить доказательство, но первый присланный вариант они назвали нечитаемым и переписали его перед публикацией.

Практика

Что получишь
Понять, что такое экспоненциальная гипотеза и почему безымянная модель OpenAI её опровергла, а заодно оценить, насколько это меняет практику и научные работы.
Первый шаг
Прочитать 67-страничный PDF Дэна Робертса или пост Скотта Ааронсона, чтобы увидеть формулировку алгоритма и оценку последствий.
Цифры
  • —67 страниц — объём PDF Дэна Робертса
  • —800 научных работ опирались на экспоненциальную гипотезу
  • —2^(n / sqrt(log n)) — новая оценка времени алгоритма, уже не экспоненциальная
  • —с 3 до 5 процентов — настолько Скотт Ааронсон поднял личную оценку вероятности P = NP
Честно
Ролик спонсирован Warp Factories: в середине автор рекламирует облачную платформу и ссылку для раннего доступа. Полное доказательство в видео не показано, для повторения нужен PDF, который OpenAI сначала прислала авторам гипотезы в нечитаемом виде и переписала перед публикацией. Собственного платного продукта Fireship в ролике не продвигает.
Если слова незнакомы — 4 терминов

Компоненты

5 шт.

Формат: реакция на новость · для продвинутых · уверенность разметки 0.9 · источник