Датские математики нашли оптимальный алгоритм для знаменитой задачи 1852 года

Дмитрий Лобанов редактор региональной ленты новостей

Два профессора из Копенгагенского университета и DTU вместе с международными коллегами нашли оптимальный алгоритм раскраски любой карты в четыре цвета. Это первый крупный прорыв в решении знаменитой проблемы четырех красок за 30 лет. Об этом пишет сайт Phys.org.

Задача, сформулированная Фрэнсисом Гутри в 1852 году, звучит так: можно ли раскрасить любую карту не более чем четырьмя цветами так, чтобы соседние области не совпадали по цвету? Первое доказательство 1879 года оказалось ошибочным, а полное появилось лишь в 1976-м, но оно опиралось на трудно проверяемые компьютерные вычисления. В 1997 году вышло более доступное доказательство, однако алгоритм был медленным для больших карт.

Новый алгоритм, представленный на конференции FOCS'26 и получивший награду за лучшую статью, работает в линейное время: если карта содержит в 10 раз больше областей, вычисления замедляются примерно в 10 раз, а не в 100, как раньше. Секрет — в открытии, что графы содержат гораздо больше «редуцируемых конфигураций», чем считалось. Профессор Миккель Торуп из Копенгагенского университета сравнивает их с ручками, за которые можно ухватиться, чтобы начать раскраску.

Исследователи, включая Карстена Томассена из DTU, работали над задачей около десяти лет. Торуп называет это «болезнью четырех цветов»: по его оценке, не менее 1000 математиков пытались найти простое доказательство и не смогли. Новое открытие может применяться не только к плоским картам, но и к поверхностям с отверстиями, например к плавательному кругу или куску сыра с дырками.