OpenAI заявляет: гипотеза об экспоненциальном времени ложна

The Exponential Time Hypothesis Is False [pdf]

В репозитории openai/math появился препринт, который опровергает гипотезу об экспоненциальном времени (ETH) — одно из ключевых допущений современной теории сложности, на котором держатся нижние оценки для SAT и множества задач. Если доказательство выдержит проверку, часть привычных представлений о вычислительной трудности придётся пересмотреть. Работа лежит в открытом доступе вместе с сотнями других препринтов по математике.