OpenAI заявила: её ИИ опроверг гипотезу 1999 года о скорости решения сложных задач
OpenAI заявила, что её модель нашла алгоритм для сложных задач вроде судоку, расписаний и коммивояжёра, который противоречит гипотезе экспоненциального времени (ETH) 1999 года. Гипотеза говорила: с каждой новой переменной время решения в худшем случае удваивается, а у алгоритма OpenAI оно растёт медленнее. Доказательство в формате Lean лежит на GitHub, проверить может любой. Пока это лишь заявление компании, ваш планировщик быстрее не станет.
AI-обработка оригинала TG: @hiaimedia (Hi, AI • Новости технологий); редакция Hamidun News
Представьте, что вы пишете планировщик смен для склада или маршрутизатор для курьеров. Чем больше заказов и условий, тем медленнее работает программа, и в какой-то момент она просто не успевает. Информатика давно спрашивает: это недостаток наших алгоритмов или предел самой задачи? OpenAI заявила, что её внутренняя модель нашла алгоритм, который опровергает одну из главных гипотез на эту тему. Пока это именно заявление, и дальше разберём, что в нём уже понятно, а что ещё нет.
О чём спор и при чём тут судоку
Гипотеза экспоненциального времени (ETH) появилась в 1999 году. Она касается большого класса комбинаторных задач, в которых решение легко проверить, но трудно найти. Судоку — удобный пример: убедиться, что числа расставлены верно, можно за минуту. Решить такое поле быстро гораздо сложнее, особенно если оно растёт с 9×9 до 1000×1000. К этому же классу относятся составление расписаний, задача коммивояжёра и тысячи других задач из логистики, планирования и оптимизации.
Если перебирать варианты один за другим, то с каждой новой переменной максимальное время работы удваивается. Для иллюстрации: если для 50 условий нужен час, то для 51 понадобится два, для 52 — четыре. Есть и более хитрые методы, которые работают чуть быстрее. Но ETH утверждала: в худшем случае время всё равно будет расти экспоненциально. По словам OpenAI, у найденного её моделью алгоритма время растёт медленнее экспоненты. Это и противоречит гипотезе.
Как это будут проверять
Доказательство записано на языке Lean и выложено на GitHub. Lean — система формальной верификации: она машинно проверяет каждый шаг рассуждения, и верить автору на слово не нужно. Любой желающий может запустить проверку у себя. Научную группу проверяющих возглавят профессор MIT Райан Уильямс и двое авторов самой гипотезы — Рассел Импальяццо и Рамамохан Патури. То есть результат будут оценивать люди, которые лучше всех понимают, что именно должно быть опровергнуто.
Осторожность тут объяснима. В начале октября OpenAI опубликовала 722 статьи о нерешённых математических задачах. Меньше чем через сутки три работы пришлось отозвать из-за ошибки. Часть математиков раскритиковала такой подход. Лауреат Филдсовской премии Теренс Тао назвал «токсичными отходами» доказательства, которые ИИ-компании массово выпускают в гонке за бенчмарками. На этом фоне новая работа с формальной записью выглядит заметно серьёзнее, но подтверждения всё равно нужно дождаться.
Что это меняет для практиков
На ETH опираются сотни работ в теории графов, вычислительной биологии и базах данных. Многие из них доказывают, что определённые задачи нельзя решить быстрее некоторого порога. Если опровержение подтвердится, такие выводы потеряют основания, и теоретикам придётся пересматривать часть своих результатов.
Но переоценивать эффект не стоит. Из опровержения ETH не вытекают сами быстрые алгоритмы для этих задач, их придётся искать отдельно. Поэтому разработчикам планировщиков, солверов и оптимизаторов переписывать код сегодня незачем: ваш поиск расписаний быстрее не станет.
Из истории можно вынести два практических урока:
- Если ИИ выдаёт сложный результат, будь то доказательство или код, важнее всего, можно ли его проверить машиной. Формат вроде Lean превращает «звучит убедительно» в «проверено».
- Генерация стала дешёвой, а проверка осталась дорогой. Три отозванные за сутки работы показывают: узким местом станет не модель, а команда, которая проверяет её выводы.
Если Уильямс, Импальяццо и Патури найдут в доказательстве изъян, история закончится ещё одним отзывом. Если не найдут, ИИ впервые опровергнет гипотезу, на которой строились сотни работ по теории сложности.
- 21 нояб. 2026 г.OpenAI GPT-6 Cyber нашла около 35 дыр в iPhone, Mac и другой технике Apple
- 21 нояб. 2026 г.22 агента Claude шесть недель искали ответы по чёрным дырам — и решили две задачи
- 21 нояб. 2026 г.Google разделит хранение чатов и обучение Gemini: отказ без потери истории
- 21 нояб. 2026 г.Apple в macOS 27.3 beta 2 даст ограничивать доступ ИИ-агентов к файлам Mac
Вопросы и ответы по материалу
Что известно по теме: о чём спор и при чём тут судоку?
Гипотеза экспоненциального времени (ETH) появилась в 1999 году. Она касается большого класса комбинаторных задач, в которых решение легко проверить, но трудно найти. Судоку — удобный пример: убедиться, что числа расставлены верно, можно за минуту. Решить такое поле быстро гораздо сложнее, особенно если оно растёт с 9×9 до 1000×1000. К этому же классу относятся составление расписаний, задача коммивояжёра и тысячи других задач из логистики, планирования и оптимизации.
Что известно по теме: как это будут проверять?
Доказательство записано на языке Lean и выложено на GitHub. Lean — система формальной верификации: она машинно проверяет каждый шаг рассуждения, и верить автору на слово не нужно. Любой желающий может запустить проверку у себя. Научную группу проверяющих возглавят профессор MIT Райан Уильямс и двое авторов самой гипотезы — Рассел Импальяццо и Рамамохан Патури. То есть результат будут оценивать люди, которые лучше всех понимают, что именно должно быть опровергнуто. Осторожность тут объяснима.
Что известно по теме: что это меняет для практиков?
На ETH опираются сотни работ в теории графов, вычислительной биологии и базах данных. Многие из них доказывают, что определённые задачи нельзя решить быстрее некоторого порога. Если опровержение подтвердится, такие выводы потеряют основания, и теоретикам придётся пересматривать часть своих результатов. Но переоценивать эффект не стоит. Из опровержения ETH не вытекают сами быстрые алгоритмы для этих задач, их придётся искать отдельно.
Протестируйте новые LLM и мультимодальные модели в одном окне
Платформа Nomad AI (nomadnet.ai) даёт прямой доступ к Claude Opus 5.5, GPT-6, Gemini 3.1, DeepSeek и автономным агентам без VPN, зарубежных карт и зоопарка подписок.
Главное из мира ИИ — раз в неделю
7 ключевых событий недели, отобранных вручную. Без шума, репостов и пресс-релизов.
Готово! Проверьте почту — мы отправили подтверждение.