Иногда для крупного результата хватает не гениальной идеи, а простого упрямства и пары часов свободного времени.
Речь о задаче теории графов, которая касается распределения нагрузки в сетях — дорожных, логистических, компьютерных. Формулировка звучит сухо, но смысл понятен любому, кто хоть раз распределял ресурсы: представьте склад, откуда грузы едут по разным маршрутам, и каждый маршрут имеет предел пропускной способности. Математически удобно допускать, что один груз можно дробить между несколькими путями — так проще найти оптимальное распределение на бумаге. Но в реальности груз обычно едет целиком, одним маршрутом.
Вопрос, который не давал покоя специалистам почти три десятилетия, звучал так: если идеальное дробное решение существует, можно ли всегда подобрать для каждого груза один цельный путь так, чтобы нагрузка на дороги почти не выросла — максимум на размер самого крупного груза. Интуитивно кажется, что да, ведь дробное решение и так близко к оптимальному. Именно эту теорию много лет пытались либо строго доказать, либо опровергнуть примером, где логика ломается.
Разобраться в вопросе помог математик Дмитрий Рыбин, который защитил диссертацию по ИИ в Китае и сейчас живет в Шэньчжэне. Он обратился к языковой модели с просьбой найти контрпример — ситуацию, где утверждение не работает. Первая реакция модели была отказом: задача выглядела слишком масштабной для короткого диалога. Но после нескольких настойчивых просьб не сдаваться модель начала выстраивать цепочку рассуждений и спустя пару часов выдала конкретную конструкцию сети, которая нарушала гипотезу.
Источник: hi-tech.mail.ru