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

Вскоре после заявления OpenAI собственное исследование, также ставящее ETH под сомнение, представила Anthropic. Если результаты обеих компаний подтвердятся, это может возобновить поиск более эффективных алгоритмов для задач, которые десятилетиями считались крайне трудными.

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

Райан Уильямс: повод серьёзнее задуматься о равенстве P = NP

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

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

Уильямс также отметил, что возможным практическим следствием открытия станут более быстрые алгоритмы. При этом ранее он говорил, что не верит в справедливость ETH.

Гэри Маркус: это может быть крупным событием

Гэри Маркус, почётный профессор Нью-Йоркского университета и известный критик чрезмерно оптимистичных оценок возможностей ИИ, отреагировал на заявление OpenAI сдержанно.

В публикации в X он назвал результат потенциально значительным — если он подтвердится. Таким образом, Маркус признал возможную важность заявления, не объявляя его доказанным.

Джон Кук: проблема P = NP остаётся открытой

Математик и консультант в области прикладной математики Джон Кук подчеркнул, что даже впечатляющие результаты OpenAI не означают решения одной из главных задач информатики.

«Статус P = NP по-прежнему неизвестен», — написал он в своём блоге.

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

Иными словами, опровержение ETH само по себе не доказывает равенство P = NP: это разные утверждения, и между ними остаётся существенная дистанция.

Джошуа Фонсека Ривера: мы могли недооценивать возможности компьютеров

Исследователь безопасности ИИ в Anthropic Джошуа Фонсека Ривера увидел в заявлении напоминание о том, что люди могут недооценивать вычислительные системы.

«Горький урок» — идея о том, что в долгосрочной перспективе методы, использующие масштабные вычисления, нередко превосходят подходы, основанные на вручную заложенных человеческих знаниях, — по его мнению, должен был подготовить исследователей к подобным открытиям.

«Я понимаю это логически, но… вау, мы действительно ничего не знаем», — написал Ривера в X.

Тимоти Гауэрс: «Очень удивительно и значимо, что это неверно»

Математик и лауреат Филдсовской премии Тимоти Гауэрс, занимающий профессорскую должность в Коллеж де Франс, кратко прокомментировал происходящее в X.

«Очень удивительно и значимо, что это неверно», — написал он, имея в виду экспоненциальную гипотезу времени.

Дэн Шиппер пожалел, что не изучал передовую математику

Глава технологического стартапа Every Дэн Шиппер отреагировал на новость с самоиронией. Он написал, что жалеет, что не получил докторскую степень в области передовой математики.

«Не то чтобы я когда-либо всерьёз собирался её получать, но всё же», — добавил Шиппер.

Что будет дальше

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

Если гипотеза ETH действительно окажется неверной, это может изменить представления о том, насколько эффективно можно решать некоторые вычислительные задачи. Но из этого не следует, что все сложные задачи внезапно станут простыми или что проблема P = NP уже решена.

Главный вопрос теперь — удастся ли независимо подтвердить результаты и понять, какие именно новые алгоритмические возможности они открывают.