ИИ-лаборатории заявляют, что опровергли гипотезу экспоненциального времени: что это значит

Это одно из трёх решений давних математических задач, которые OpenAI опубликовала одновременно. Anthropic через несколько часов выложила собственное опровержение. Разбор результата среди специалистов по информатике организует Райан Уильямс, профессор MIT (Массачусетский технологический институт).

Передовые ИИ-лаборатории заявляют, что их модели опровергли гипотезу экспоненциального времени. Что это значит на практике? До сих пор на этом допущении строилось понимание того, какие задачи компьютер в принципе не может решить быстро. Теперь его оспаривают две компании, разработавшие ChatGPT и Claude. Подробности публикует TechCrunch.

Что измеряли: почему решение одних задач занимает годы, а проверка секунды?

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

P равно NP означает, что вы можете не только проверить решение судоку, но и просто сгенерировать его. И это верно для любой задачи, которую можно быстро проверить. Звучит слишком хорошо, чтобы быть правдой. : Райан Уильямс, профессор MIT

На этой разнице держится шифрование. С ключом сообщение открывается мгновенно, а подбор ключа занимает столько времени, что теряет смысл. Поэтому большинство учёных исходит из того, что P не равно NP.

Гипотеза экспоненциального времени (Exponential Time Hypothesis, ETH) служила доводом в пользу этой позиции. Она утверждает, что для особого класса сложных логических головоломок даже самому быстрому алгоритму (пошаговому рецепту решения) нужно лавинообразно больше времени по мере роста числа переменных. Каждая новая переменная не прибавляет работу, а умножает её.

Что обнаружили: модели предложили путь быстрее «лавины»

• OpenAI и Anthropic утверждают, что их модели нашли алгоритмы, которые решают такие головоломки за «субэкспоненциальное» время, то есть быстрее, чем считалось возможным. Если это подтвердится, гипотеза опровергнута.
• Решение ETH стало одним из 3 опубликованных OpenAI. Задачи относятся к трём областям: математике, информатике и физике.
• Каждой области OpenAI передала работу своим способом. Математикам выложили её на GitHub (сервис, где программисты публикуют код). Специалисты по информатике собрали рабочую группу и попросили открыть доказательства и профинансировать конференцию. Физики сами решат, как выпускать результат.
• Уильямс помогает толковать решение вместе с Расселом Импальяццо и Рамамоханом Патури из Калифорнийского университета в Сан-Диего. Именно они впервые опубликовали гипотезу в 1999 году.
• По словам Уильямса, в доказательстве есть два или три «чужеродных на вид» фрагмента. Именно они, а не рутинные части, убедили его, что над результатом должно работать всё сообщество.

Первым шагом группа выпустила открытое письмо. В нём учёных просят присылать отзывы и обсудить правила учёта вклада ИИ в науку.

Обращает на себя внимание перемена позиции Уильямса. В октябре он назвал предыдущий массовый выброс доказательств от OpenAI «DDoS-атакой на математиков» (DDoS: атака, при которой сервис заваливают потоком запросов, пока он не перестанет справляться). Теперь он согласился сотрудничать, чтобы помочь довести важные для области идеи.

Сам Уильямс оценивает последствия сдержанно:

Каждому специалисту по информатике, вероятно, стоит придать чуть больше веса правдоподобию равенства P и NP, но у каждого этот вес будет свой. : Райан Уильямс, профессор MIT

Если результат устоит, многие научные работы последнего десятилетия, опиравшиеся на ETH, придётся пересматривать. Именно поэтому Уильямс добивался от OpenAI поддержки конференции.

Что это значит для вас?

Автору Дзена эта история даёт образец честной подачи. Пишите «заявляют» и «утверждают», а не «доказали»: учёные ещё проверяют результат. Аналогию с судоку можно брать для любого текста о сложности вычислений, читатель поймёт её без формул.

Маркетологу стоит запомнить другое. ИИ уже участвует в фундаментальной науке, но за каждым громким заявлением следует спор об авторстве. Обещание «нейросеть сама всё придумала» в рекламе рискует вызвать такие же вопросы.

Предпринимателю и обычному пользователю: по проверке OpenAI, банковские карты и мессенджеры от этого открытия не стали менее защищёнными. Чтобы разобраться в сложном термине, можно попросить доступные в РФ YandexGPT или GigaChat объяснить его через бытовой пример. Затем сверьте ответ с первоисточником, ведь нейросети бывают склонны к галлюцинациям (когда ИИ уверенно выдумывает то, чего не было).

Ближайшие месяцы покажут, устоит ли опровержение. Но вопрос «а может ли машина решить быстрее?» больше не звучит наивно, и пишущим о технологиях лучше учиться объяснять его уже сегодня.

По данным TechCrunch