МЫ В СОЦСЕТЯХ:

Не могли решить почти 200 лет: математики разобрались с "проблемой четырех красок"

карта математика
Математики нашли более простое решение теоремы о проблеме четырех красок | Фото: wikipedia

Теорема, известная как "проблема четырех красок", не дает ученым покоя с 1852 года. Но теперь, похоже, математикам удалось совершить прорыв.

Формально математики решили теорему, известную как "проблема четырех красок", еще в 1976 году, однако она все еще продолжает оставаться камнем преткновения для исследователей. Увлеченность этой невероятно сложной концепцией настолько сильна, что некоторые математики даже сравнивают свою одержимость ею с затяжной болезнью, пишет Popular Science.

Однако теперь, после десяти лет анализа международная группа математиков впервые за 30 лет добилась значительного прорыва в этом вопросе. Ученые представили оптимальный и наиболее эффективный алгоритм для решения проблемы четырех красок на конференции "Основы компьютерных наук".

Отметим, что суть проблемы четырех красок обманчиво проста: в 1852 году английский математик Фрэнсис Гатри предположил, что для раскрашивания любой карты, разделенной на области, достаточно всего четырех цветов — так, чтобы соседние области были окрашены в разные цвета. Первое доказательство было предложено в 1879 году и казалось верным в течение 11 лет — впрочем, позже ученые обнаружили в расчетах ошибку.

Потребовалось более 85 лет, чтобы получить полноценное доказательство. Еще один примечательный момент: крупная теорема впервые в истории была доказана с помощью компьютерной программы. Впрочем, многие представители математического сообщества отнеслись к такому "цифровому" открытию скептически, поскольку проверить его самостоятельно оказалось крайне затруднительно.

В 1997 году появилось более доступное доказательство. Впрочем, даже в нем алгоритмический метод работал крайне медленно при увеличении сложности карт. С тех пор некоторые математики по всему миру продолжают искать новые подходы к решению этой задачи.

Потребовались годы, но ученые, похоже, таки смогли добиться успеха, обнаружив новую деталь, касающуюся поверхностей, подобных картам. Исследователи поняли, что в таких графах содержится гораздо больше "приводимых конфигураций", чем предполагали эксперты ранее. Это позволило выделить значительно более широкий набор отправных точек для решения задачи.

По словам соавтора исследования, математика из Датского технического университета Карстена Томассена, им с коллегами представили приводимые конфигурации как своего рода ручки, за которые можно ухватиться, чтобы приступить к раскрашиванию карты в четыре цвета. В результате им удалось доказать, что в графах есть не одна такая "ручка", а огромное количество. Любопытно, что ранее об этом никто не знал.

Отметим, что обнаружение этих ручек позволило начать заполнение областей четырьмя цветами одновременно, что экспоненциально ускорило весь процесс. Авторы отмечают, что благодаря этому новый алгоритм перешел от квадратичной сложности к линейной.

Другие новости науки