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