Исследователи из OpenAI представили работу, которая ставит под сомнение обоснованность гипотезы ETH (Exponential Time Hypothesis), предложенной учёными в 1999 году. Согласно этой гипотезе, известная логическая задача 3-SAT не решается существенно быстрее простого перебора вариантов. На основе этой гипотезы построены сотни научных работ в области теории графов, биоинформатики, баз данных и геометрии.

Однако новая работа OpenAI утверждает, что найден алгоритм, решающий задачу подсчёта решений 3-SAT за субэкспоненциальное время. Это означает, что сложность алгоритма растёт медленнее любой экспоненциальной зависимости от количества переменных. Поскольку подсчёт решений сложнее проверки существования хотя бы одного решения, новый метод автоматически даёт решение и второй задачи.

Открытие было сделано искусственным интеллектом OpenAI 16 октября и затем проверено вручную с помощью системы формальной верификации Lean. Исследование опубликовано на GitHub вместе с другими работами компании, часть которых ранее прошла независимую проверку.

Самостоятельную проверку открытия проводят известные учёные-компьютерщики, среди которых авторы оригинальной гипотезы — Расселл Импьяццо и Рамамохан Патури, а также профессор MIT Райан Уильямс. Они подчеркнули, что участие в проверке не является подтверждением достоверности результата, поскольку столь важное открытие требует тщательной независимой экспертизы.

Несмотря на научный характер работы, сообщество Crypto Twitter восприняло публикацию неоднозначно, связывая её с криптовалютой Ethereum. Пользователь Takumi отметил резкое снижение стоимости ETH на рынке, а Эндрю Цзян пошутил о молчании Виталика Бутерина после появления исследования. Однако представители OpenAI уточнили, что речь идёт исключительно о компьютерной гипотезе, никак не влияющей на цену криптовалюты или деятельность её создателей.

Эксперты предупреждают, что практическое применение нового алгоритма потребует дальнейших исследований, а сам результат не доказывает возможность быстрого решения других задач класса NP. Вопрос о равенстве классов P и NP остаётся открытым.