«Апостериори»: Искусственный интеллект поставил под сомнение одну из фундаментальных гипотез информатики
Новости науки и технологий
Поддержите «Эхо», если вы не в России
Нейросети компаний OpenAI и Anthropic независимо друг от друга предложили доказательства, опровергающие гипотезу экспоненциального времени. Если результаты подтвердятся, это может изменить представления учёных о сложности вычислений и привести к созданию новых алгоритмов.
Гипотеза экспоненциального времени, или ETH, была сформулирована в конце 1990-х годов. Она касается одной из фундаментальных проблем информатики: сколько вычислений необходимо компьютеру для решения определённой задачи.
В основе гипотезы лежит задача выполнимости булевых формул, известная как SAT. Допустим есть множество логических переменных, каждая из которых может принимать только два значения: истина или ложь. Эти переменные связаны между собой логическими условиями. Компьютеру необходимо определить, существует ли хотя бы одна комбинация значений, при которой все условия выполняются одновременно.
В простейшем случае можно последовательно проверить все возможные комбинации. Однако их количество увеличивается экспоненциально. Для десяти переменных существует 1024 комбинации, для двадцати – уже больше миллиона, а для ста – число, превышающее количество атомов в человеческом теле.
Гипотеза ETH утверждает, что для определённого класса подобных задач, известного как 3-SAT, не существует алгоритма, который решал бы все возможные случаи за субэкспоненциальное время. Иными словами, предполагается, что даже самый эффективный алгоритм не сможет избежать экспоненциального роста времени вычислений по мере увеличения числа переменных.
Это предположение на протяжении десятилетий использовалось для оценки сложности множества других вычислительных задач. Например, поиска оптимальных маршрутов, обработки больших массивов данных, решения задач биоинформатики и оптимизации компьютерных систем. Опираясь на ETH, исследователи могли обосновывать, почему для определённых задач не стоит ожидать существенно более быстрых алгоритмов.
С той же гипотезой связана и современная криптография. Надёжность многих криптографических систем основана на том, что некоторые вычисления крайне трудно выполнить за приемлемое время. Однако гипотеза ETH не является непосредственной основой безопасности большинства современных алгоритмов шифрования. Поэтому её опровержение само по себе не означает, что существующие способы защиты информации окажутся ненадёжными.
26 октября 2026 года компания OpenAI опубликовала работу под названием «Гипотеза экспоненциального времени ложна». Согласно публикации, разработанная компанией модель искусственного интеллекта обнаружила новый алгоритм, позволяющий решать задачу SAT за субэкспоненциальное время. Более того, алгоритм способен не только определить существование решения, но и подсчитать количество всех подходящих комбинаций.
Практически одновременно компания Anthropic опубликовала собственную работу, подготовленную с помощью исследовательской версии модели Claude. По утверждению компании, ключевой алгоритм был найден ещё 16 октября, в тот же день, когда результат получила модель OpenAI. При этом исследования проводились независимо друг от друга.
Оба доказательства также были представлены на языке Lean, позволяющем компьютеру формально проверять математические рассуждения. В отличие от обычного текста, такая запись позволяет проверить логическую корректность каждого шага доказательства.
Однако это ещё не означает, что гипотеза окончательно опровергнута. Необходимо также удостовериться, что формально доказанные утверждения действительно соответствуют исходной математической проблеме и что при переходе от одной модели вычислений к другой не возникает неучтённых ограничений.
Для независимой проверки была организована группа исследователей во главе с Расселом Импальяццо, Рамамоханом Патури из Калифорнийского университета в Сан-Диего и Райаном Уильямсом из Массачусетского технологического института. Примечательно, что Импальяццо и Патури сами участвовали в разработке гипотезы ETH.
В опубликованном 26 октября обращении исследователи подчеркнули, что их участие в проверке не означает подтверждения результатов OpenAI.
Тем не менее уже 30 октября один из авторов первоначальной гипотезы, Фрэнсис Зейн, сообщил, что несколько независимых исследователей смогли воспроизвести проверку доказательств в Lean. В начале ноября появились и дополнительные отчёты, подтверждающие успешное прохождение формальной проверки.
12 ноября организаторы опубликовали исходный запрос, с помощью которого OpenAI получила свой результат. Однако окончательного заключения о правильности доказательств экспертная группа пока не представила.
Даже если результаты подтвердятся, это не означает немедленной революции в информационных технологиях. Предложенные алгоритмы остаются чрезвычайно ресурсоёмкими. Более того, согласно одной из последующих оценок, преимущество алгоритма OpenAI перед полным перебором может проявляться лишь при настолько огромном количестве переменных, что практическое использование пока невозможно.
Но математическое значение результата от этого не становится меньше. Подтверждение доказательств означало бы, что целый класс задач допускает принципиально более быстрые алгоритмы, чем предполагалось ранее. Это заставит исследователей пересмотреть множество существующих оценок вычислительной сложности.
Наконец, открытие связано с одной из самых известных нерешённых проблем математики – равенством классов P и NP. Она ставит вопрос: можно ли любую задачу, решение которой легко проверить, также быстро решить?
Опровержение ETH не доказывает равенство P и NP. Субэкспоненциальные алгоритмы по-прежнему могут требовать существенно больше вычислений, чем полиномиальные. Однако новые результаты показывают, что некоторые ограничения, считавшиеся фундаментальными на протяжении десятилетий, возможно, вовсе не существуют.
Если независимая проверка подтвердит доказательства, это станет не только важным открытием в теории вычислительной сложности, но и одним из наиболее убедительных примеров способности искусственного интеллекта самостоятельно получать принципиально новые научные результаты.

