Интенсив 21–22.11 · БесплатноБесплатный 2-дневный интенсив по вайбкодингу 21–22 ноября в 16:00 МСК (Сб–Вс) · Живой Поток 3 стартует 23.11Записаться бесплатно →Поток 3 (23.11)
Безопасность и правоРазбор · На радарTG: @hiaimedia (Hi, AI • Новости технологий)→ оригинал

OpenAI заявила: её ИИ опроверг гипотезу 1999 года о скорости решения сложных задач

OpenAI заявила, что её модель нашла алгоритм для сложных задач вроде судоку, расписаний и коммивояжёра, который противоречит гипотезе экспоненциального времени (ETH) 1999 года. Гипотеза говорила: с каждой новой переменной время решения в худшем случае удваивается, а у алгоритма OpenAI оно растёт медленнее. Доказательство в формате Lean лежит на GitHub, проверить может любой. Пока это лишь заявление компании, ваш планировщик быстрее не станет.

AI-обработка оригинала TG: @hiaimedia (Hi, AI • Новости технологий); редакция Hamidun News
OpenAI заявила: её ИИ опроверг гипотезу 1999 года о скорости решения сложных задач
Источник: TG: @hiaimedia (Hi, AI • Новости технологий). Коллаж: Hamidun News.
Слушать статью
Паспорт материала и цифры
ПараметрДанные
ПервоисточникTG: @hiaimedia (Hi, AI • Новости технологий) ↗
Главный редактор
Ключевой факт #1Проверку возглавят Райан Уильямс из MIT и двое авторов ETH
Ключевой факт #2На ETH опираются сотни работ по графам, биологии и базам данных
Ключевой факт #3В начале октября три из 722 статей OpenAI отозвали из-за ошибки

Представьте, что вы пишете планировщик смен для склада или маршрутизатор для курьеров. Чем больше заказов и условий, тем медленнее работает программа, и в какой-то момент она просто не успевает. Информатика давно спрашивает: это недостаток наших алгоритмов или предел самой задачи? OpenAI заявила, что её внутренняя модель нашла алгоритм, который опровергает одну из главных гипотез на эту тему. Пока это именно заявление, и дальше разберём, что в нём уже понятно, а что ещё нет.

О чём спор и при чём тут судоку

Гипотеза экспоненциального времени (ETH) появилась в 1999 году. Она касается большого класса комбинаторных задач, в которых решение легко проверить, но трудно найти. Судоку — удобный пример: убедиться, что числа расставлены верно, можно за минуту. Решить такое поле быстро гораздо сложнее, особенно если оно растёт с 9×9 до 1000×1000. К этому же классу относятся составление расписаний, задача коммивояжёра и тысячи других задач из логистики, планирования и оптимизации.

Если перебирать варианты один за другим, то с каждой новой переменной максимальное время работы удваивается. Для иллюстрации: если для 50 условий нужен час, то для 51 понадобится два, для 52 — четыре. Есть и более хитрые методы, которые работают чуть быстрее. Но ETH утверждала: в худшем случае время всё равно будет расти экспоненциально. По словам OpenAI, у найденного её моделью алгоритма время растёт медленнее экспоненты. Это и противоречит гипотезе.

Как это будут проверять

Доказательство записано на языке Lean и выложено на GitHub. Lean — система формальной верификации: она машинно проверяет каждый шаг рассуждения, и верить автору на слово не нужно. Любой желающий может запустить проверку у себя. Научную группу проверяющих возглавят профессор MIT Райан Уильямс и двое авторов самой гипотезы — Рассел Импальяццо и Рамамохан Патури. То есть результат будут оценивать люди, которые лучше всех понимают, что именно должно быть опровергнуто.

Осторожность тут объяснима. В начале октября OpenAI опубликовала 722 статьи о нерешённых математических задачах. Меньше чем через сутки три работы пришлось отозвать из-за ошибки. Часть математиков раскритиковала такой подход. Лауреат Филдсовской премии Теренс Тао назвал «токсичными отходами» доказательства, которые ИИ-компании массово выпускают в гонке за бенчмарками. На этом фоне новая работа с формальной записью выглядит заметно серьёзнее, но подтверждения всё равно нужно дождаться.

Что это меняет для практиков

На ETH опираются сотни работ в теории графов, вычислительной биологии и базах данных. Многие из них доказывают, что определённые задачи нельзя решить быстрее некоторого порога. Если опровержение подтвердится, такие выводы потеряют основания, и теоретикам придётся пересматривать часть своих результатов.

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

Из истории можно вынести два практических урока:

  • Если ИИ выдаёт сложный результат, будь то доказательство или код, важнее всего, можно ли его проверить машиной. Формат вроде Lean превращает «звучит убедительно» в «проверено».
  • Генерация стала дешёвой, а проверка осталась дорогой. Три отозванные за сутки работы показывают: узким местом станет не модель, а команда, которая проверяет её выводы.

Если Уильямс, Импальяццо и Патури найдут в доказательстве изъян, история закончится ещё одним отзывом. Если не найдут, ИИ впервые опровергнет гипотезу, на которой строились сотни работ по теории сложности.

Сюжет

Вопросы и ответы по материалу

Что известно по теме: о чём спор и при чём тут судоку?

Гипотеза экспоненциального времени (ETH) появилась в 1999 году. Она касается большого класса комбинаторных задач, в которых решение легко проверить, но трудно найти. Судоку — удобный пример: убедиться, что числа расставлены верно, можно за минуту. Решить такое поле быстро гораздо сложнее, особенно если оно растёт с 9×9 до 1000×1000. К этому же классу относятся составление расписаний, задача коммивояжёра и тысячи других задач из логистики, планирования и оптимизации.

Что известно по теме: как это будут проверять?

Доказательство записано на языке Lean и выложено на GitHub. Lean — система формальной верификации: она машинно проверяет каждый шаг рассуждения, и верить автору на слово не нужно. Любой желающий может запустить проверку у себя. Научную группу проверяющих возглавят профессор MIT Райан Уильямс и двое авторов самой гипотезы — Рассел Импальяццо и Рамамохан Патури. То есть результат будут оценивать люди, которые лучше всех понимают, что именно должно быть опровергнуто. Осторожность тут объяснима.

Что известно по теме: что это меняет для практиков?

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

ЖХ
Жемал Хамидун — CPO Alpina Digital, продакт-менеджер AlpinaGPT. Делает AI-продукты с 2019 года. Hamidun News — pet project, который вырос в production-агрегатор с 6000+ читателей.
✦ Единое AI-пространство · Nomad

Протестируйте новые LLM и мультимодальные модели в одном окне

Платформа Nomad AI (nomadnet.ai) даёт прямой доступ к Claude Opus 5.5, GPT-6, Gemini 3.1, DeepSeek и автономным агентам без VPN, зарубежных карт и зоопарка подписок.

Открыть Nomad AI →Автономный Nomad Agent
Что вы думаете?
Загружаем комментарии…