Два профессора из Копенгагенского университета и DTU вместе с международными коллегами нашли оптимальный алгоритм для знаменитой задачи о четырёх красках, над которой математики бились 174 года. Работа опубликована на сервере препринтов arXiv. Об этом пишет сайт Phys.org.
Задача возникла в 1852 году, когда английский математик Фрэнсис Гатри заметил, что для карты графств Англии ему хватило четырёх цветов. Первое доказательство появилось в 1879 году, но через 11 лет в нём нашли ошибку. Полное доказательство было получено в 1976 году, однако оно опиралось на компьютерные расчёты, которые было трудно проверить. В 1997 году появилось более доступное доказательство, но алгоритм работал медленно на больших картах.
Новый алгоритм, по словам профессора Миккеля Торупа из Копенгагенского университета, «эффективен и даёт гораздо более быстрый способ раскраски». Первая часть работы была представлена на конференции FOCS'26 и получила награду за лучшую статью.
Исследователи, включая Карстена Томассена, Кен-ичи Каварабаяши и Бояна Могара, работали над задачей около 10 лет. Торуп называет это «болезнью четырёх красок»: по его оценке, не менее 1000 математиков пытались найти простое доказательство и не смогли.
Прорыв основан на новом математическом открытии: в графах гораздо больше «сводимых конфигураций», чем считалось. Это позволяет начинать раскраску из многих точек и ускоряет процесс. Время вычислений сократилось с квадратичного до линейного: если карта содержит в 10 раз больше областей, вычисления становятся медленнее примерно в 10 раз, а не в 100, как раньше.
Новый метод применим не только к плоским картам, но и к поверхностям с отверстиями, например, к плавательному кругу или куску сыра с дырками. Учёные считают, что результат может иметь значение далеко за пределами теоремы о четырёх красках.