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

Что в ролике
Физик 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 терминов
- 3-SATзадача выполнимости булевых формул с тремя переменными в каждом условии, эталонная NP-полная задача
- ETHгипотеза экспоненциального времени: предположение, что 3-SAT нельзя решить быстрее экспоненты
- P = NPвопрос, можно ли все задачи с быстрой проверкой решения решать так же быстро; равенство сломало бы криптографию
- интерполяция Эрмитаматематический метод XIX века, который восстанавливает точное значение функции по нескольким точкам
Компоненты
5 шт.Формат: реакция на новость · для продвинутых · уверенность разметки 0.9 · источник