Модель OpenAI опровергла гипотезу, на которой держалась теория сложности

OpenAI объявила, что её внутренняя модель решила три открытые задачи — в математике, теоретической информатике и физике. Главный результат: опровержение гипотезы об экспоненциальном времени (ETH) — предположения, что задачу выполнимости булевых формул нельзя решить заметно быстрее полного перебора. На ETH десятилетиями опирались доказательства нижних границ сложности: если задачу нельзя ускорить, то и производные от неё — тоже.

Второй результат — гипотеза Кристофера Согге о локальном сглаживании, открытая с 1991 года: модель построила доказательство для пространств любой размерности, из него следуют и гипотезы Какеи и Стейна. Тексты выложены вместе с формализацией в Lean — языке, на котором доказательство проверяет компьютер, а не рецензент.

По данным Telegram-каналов, опровержение ETH почти одновременно получили внутренние модели OpenAI и Anthropic, обе компании опубликовали препринты. Результаты сейчас проверяют эксперты; практические последствия для криптографии и алгоритмов пока никто не оценил.