GPT-5.6 закрыла 30-летний пробел в теории выпуклой оптимизации

Филлип Кергер, преподаватель-профессор факультета IEOR (исследование операций и инженерия) в UC Berkeley с PhD по прикладной математике, опубликовал на Reddit (перепост попал на Hacker News, 543 балла, 348 комментариев) рассказ о том, как модель GPT-5.6 Sol Pro закрыла математический вопрос, остававшийся открытым 30 лет. Речь о задаче теории сложности: детерминированная оптимизация выпуклой функции по значениям без градиента (zeroth-order/derivative-free convex optimization). Дана выпуклая 1-липшицева функция f на единичном шаре в d-мерном пространстве; алгоритм может запрашивать точку x и получать в ответ только число f(x) (никакой другой информации, например градиента). Вопрос, сколько таких запросов Q(d, ε) нужно в худшем случае, чтобы найти точку, близкую к минимуму с точностью ε. В 1996 году Протасов показал, что порядка d² запросов достаточно (верхняя оценка). Но нижняя оценка сложности практически отсутствовала: лучшее, что было известно, Ω(d), унаследованное из более сильной модели первого порядка (где алгоритм получает ещё и градиент). Из-за этого 30 лет было неизвестно, есть ли выигрыш от более слабой модели без градиента, то есть существует ли алгоритм с числом запросов порядка d вместо d². Кергер сам работал над этой задачей около года, пробовал безуспешно, в том числе с GPT-5.4 и GPT-5.5. После публикации OpenAI доказательства гипотезы о двойном покрытии циклов (Cycle Double Cover Conjecture, CDC) он адаптировал ту же методику промптинга: составил инструкцию для модели объёмом около 10 страниц, детально описывающую подходы и порядок действий, по образцу промпта OpenAI для CDC (сам этот промпт тоже приложен к материалам). Он задал модели цель, доказать квадратичную нижнюю оценку при точности порядка d⁻⁴. За 148 минут непрерывной работы в веб-интерфейсе GPT-5.6 Sol Pro выдала доказательство квадратичной нижней оценки при чуть более слабой точности порядка d⁻³, то есть фактически показала, что алгоритм Протасова 1996 года (d² запросов) близок к оптимальному, и градиент здесь принципиально помогает, закрывая тем самым разрыв, продержавшийся три десятилетия. Кергер проверил доказательство и формализовал его в системе Lean, доказательство прошло формальную верификацию. Конструкция и ключевой инвариант, по его словам, содержательно перекликаются с классическим результатом Немировского и Юдина для оптимизации первого порядка (обе используют функции вида максимума аффинных функций). На GitHub выложены препринт, код на Lean, полный текст использованных промптов, карта доказательства и ссылки на исходные переписки с моделью; статья также подана как препринт на arXiv, но рецензирование ещё не пройдено. Автор специально уточняет: это была именно версия Sol Pro, а не Sol Ultra. В заключение Кергер даёт свою оценку возможностей ИИ: по его мнению, найти правильную конструкцию (класс сложных функций и стратегию "противника") для таких нижних оценок, самая трудная часть, а дальнейшее доказательство обычно опирается на уже известную технику из теории выпуклой геометрии. Он не считает, что модель создала принципиально новую математику, скорее умело применила существующий инструментарий. Вывод автора: если результат достижим существующими техниками, современный ИИ сможет его получить, поэтому исследователям в математике и теории сложности вычислений больше не имеет смысла заниматься "низко висящими" и даже "средне висящими" задачами, люди останутся нужны там, где требуются подлинно новые подходы.

Ключевые факты

Профессор IEOR UC Berkeley Филлип Кергер доказал (с помощью GPT-5.6 Sol Pro) нижнюю оценку сложности для оптимизации выпуклой функции по значениям без градиента (zeroth-order convex optimization), вопрос, открытый с 1996 года
До этого нижняя оценка была лишь Ω(d), унаследованная из более сильной модели с градиентом; верхняя оценка (~d² запросов) была известна с 1996 года благодаря алгоритму Протасова
GPT-5.6 Sol Pro за 148 минут непрерывной работы по 10-страничному промпту (по образцу промпта OpenAI для доказательства гипотезы о двойном покрытии циклов) выдала доказательство квадратичной нижней оценки при точности порядка d⁻³
Доказательство формально верифицировано в системе Lean; препринт, Lean-код, полные промпты и переписки с моделью выложены на GitHub, статья подана на arXiv, но рецензирование ещё не пройдено
Автор считает, что модель применила существующую технику, а не создала новую математику: по его выводу, ИИ теперь способен закрывать задачи, решаемые известными методами, а математикам-людям останутся задачи, требующие подлинно новых подходов

Почему это важно

Это ещё один публичный случай, когда современная модель (после доказательства OpenAI гипотезы о двойном покрытии циклов) самостоятельно закрывает открытый вопрос теории сложности, который профессиональный математик с профильным PhD не смог решить сам за год работы и с помощью более ранних версий модели (GPT-5.4, GPT-5.5). Разрыв в 30 лет, не техническая мелочь, а фундаментальный вопрос о том, помогает ли градиент в выпуклой оптимизации в принципе.

Кому это важно

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

Как это применить

Прямого продукта или цены здесь нет, это математический результат. Практический вывод: для задач оптимизации по значениям функции без градиента в d измерениях число необходимых запросов принципиально порядка d², и алгоритм Протасова 1996 года уже близок к оптимальному, искать более экономный алгоритм бессмысленно. Методика тоже воспроизводима: автор выложил весь промпт (10 страниц), Lean-формализацию и переписки с моделью на GitHub, так что подход можно повторить для других открытых нижних оценок.

Можно ли доверять

Сильный сигнал доверия, доказательство формально верифицировано в системе Lean, а не принято на слово; автор дополнительно проверил его сам как специалист по нижним оценкам сложности в своей области. Против этого, результат опубликован как препринт и ещё НЕ прошёл рецензирование; проверку и формализацию делал сам автор-заявитель, а не независимая сторона; итоговая точность доказательства (d⁻³) оказалась слабее изначально запрошенной (d⁻⁴). Обсуждение на Hacker News активное (543 балла, 348 комментариев), но это не заменяет рецензирование.

Риски и подводные камни

Автор сам предупреждает: модель не создала принципиально новую математику, а умело собрала доказательство из уже известных техник теории выпуклой геометрии, это ограничивает выводы о "творческих" способностях ИИ. Формальная верификация в Lean подтверждает корректность записанного в системе утверждения, но не отменяет риск, что формализация не полностью отражает содержательную формулировку задачи, изложенную в тексте. Также стоит учитывать эффект отбора: публично освещаются успешные попытки (эта и более ранняя с CDC), а сколько похожих экспериментов с другими открытыми задачами не дали результата, неизвестно.

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

— Филлип Кергер, автор препринта, профессор IEOR UC Berkeley