Наука 22 октября 2026, 20:33 МСК

Исследователи Microsoft с помощью ИИ доказали гипотезу KLS 1995 года

Чжао Сун и Синьчжи Чжан из Microsoft Research сообщили о доказательстве гипотезы Каннана — Ловаса — Симоновитса, применив ИИ-агентов для поиска идей и проверки рассуждений.

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

Несколько ИИ-агентов параллельно изучали разные подходы, проводили объёмные вычисления, включая тензоры высокого порядка, и нашли перспективный критерий; всего исследователи рассмотрели более 100 вариантов. Ключевые шаги — рекурсивное применение критерия и оценку суммарной ошибки — сделали люди. По данным Microsoft, попытки решить задачу без участия человека при сопоставимом бюджете токенов не удались.

Результат подкреплён независимыми доказательствами, появившимися параллельно, и формализацией в Lean 4.

• Гипотеза сформулирована в 1995 году
• Рассмотрено более 100 подходов
• Доказательство формализовано в Lean 4