Выпускник факультета математики НИУ ВШЭ Дмитрий Рыбин представил контрпример к гипотезе Диница — Гарга — Гоеманса, которая оставалась нерешенной около 30 лет. Как следует из Реестра дипломов НИУ ВШЭ, в работе над задачей исследователю помогла модель GPT-5.6 Pro. По словам самого Рыбина, он несколько раз просил нейросеть не прекращать поиск решения, прежде чем удалось получить полноценный результат.
Читайте: Россиянам готовят новые запреты: что изменится уже в ближайшее время
Исследование относится к теории сетевых потоков. В упрощенном виде задача заключается в проверке того, можно ли преобразовать идеальную математическую модель, допускающую разделение потока между несколькими маршрутами, в систему реальных неделимых путей без дополнительных затрат и при ограниченном превышении нагрузки. Именно такая возможность предполагалась гипотезой Диница — Гарга — Гоеманса.
С первой попытки модель не смогла найти полный контрпример. Тогда исследователь продолжил работу с нейросетью, предложив ей довести поиск до конца и добиться прорыва. В опубликованной переписке содержится лишь несколько коротких запросов, после которых GPT-5.6 Pro построила небольшой ориентированный граф, ставший основой для опровержения гипотезы.
Полученный пример показал, что стоимость дробного потока в построенном графе составляет 58, тогда как любой допустимый неделимый вариант при заданном ограничении нагрузки требует затрат не менее 60. Этого оказалось достаточно, чтобы продемонстрировать несостоятельность исходного утверждения, которое на протяжении нескольких десятилетий оставалось открытым.
Дмитрий Рыбин связан с Нижним Тагилом, окончил математическую программу НИУ ВШЭ, а затем продолжил обучение в Китайском университете Гонконга. Ранее он уже занимался исследованиями в области комбинаторики, оптимизации и алгоритмов с использованием методов машинного обучения.
Модели сетевых потоков применяются при анализе транспортных, логистических и компьютерных сетей. При этом полученный результат не предлагает готового способа решения, например, проблемы автомобильных заторов. Его практическое значение заключается в том, что разработчикам алгоритмов теперь придется учитывать: переход от идеализированных математических моделей к реальным неделимым маршрутам в отдельных случаях неизбежно сопровождается дополнительными затратами или увеличением нагрузки. На данный момент контрпример и переписка с искусственным интеллектом опубликованы в открытом доступе, однако результат пока не прошел полноценное рецензирование и формальную верификацию.
Читайте также:
- Россиянам грозят новые начисления за ЖКХ: вступили в силу важные изменения
- Пенсии в России резко вырастут с 1 августа: кто получит прибавку уже летом
- Миллионы россиян столкнутся с новыми правилами: что изменится для ваших денег
