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

Компания OpenAI опубликовала результаты, согласно которым гипотеза об экспоненциальном времени (ETH) является ложной. Это открытие ставит под сомнение корректность множества предыдущих теоретических выводов в области теории сложности вычислений, которые опирались на истинность данной гипотезы.