Міжнародна команда математиків уперше за три десятиліття домоглася серйозного прориву в знаменитій задачі про чотири кольори. На конференції Foundations of Computer Science (FOCS) дослідники представили оптимальний, найефективніший на сьогодні алгоритм, який розв’язує цю задачу, повідомляє Popular Science.

Задача про чотири кольори формулюється так: щоб зафарбувати будь-яку плоску карту, достатньо лише чотирьох кольорів так, аби сусідні області не мали однакового кольору. Попри уявну простоту, ця ідея вже понад 170 років не дає спокою математикам і навіть отримала в середовищі фахівців жартівливу назву «чотирикольорова хвороба».
Як виникла задача про чотири кольори
У 1852 році англійський математик Френсіс Ґатрі (Francis Guthrie) висунув припущення, що будь-яку карту можна розфарбувати лише чотирма фарбами. Уявімо всі країни, штати чи регіони на площині, зафарбовані чотирма кольорами так, щоб жодні дві сусідні області не збігалися за кольором — саме це й описує задача.
Перше «доведення» з’явилося в 1879 році й вважалося коректним протягом 11 років, доки колеги Ґатрі не виявили помилку в обчисленнях. Повноцінний доказ з’явився лише більш ніж через 85 років і став історичним: це була одна з перших великих теорем, доведених за допомогою комп’ютерної програми.
Однак частина математичної спільноти поставилася до такого результату скептично — перевірити всі кроки машинного доведення було надзвичайно складно. У 1997 році з’явився більш «людяний» варіант доказу, але пов’язаний із ним алгоритм сильно сповільнювався зі зростанням розміру карти.
Відтоді лише небагато дослідників продовжували шукати нові підходи. Серед них — комп’ютерний науковець Міккель Торуп (Mikkel Thorup) з Копенгагенського університету, який порівнює свою багаторічну зацікавленість із «чотирикольоровою хворобою».
Новий погляд на планарні графи
Прорив став можливим завдяки аналізу так званих планарних графів — абстрактних «карто-подібних» структур, де вершини та ребра можна зобразити на площині без перетинів. Торуп і його колеги виявили в них важливу деталь: таких графів існує набагато більше «скорочуваних» конфігурацій, ніж вважалося раніше.
Ці конфігурації дослідники описують як своєрідні «ручки», за які можна «вхопитися», щоб почати чотириколірне розфарбування. Співавтор роботи, математик Карстен Томассен (Carsten Thomassen) з Технічного університету Данії (DTU), пояснює, що раніше вважалося, ніби в графі є лише одна-дві такі «ручки», тоді як новий аналіз показав їх вражаюче багато.
Замість одиничних точок старту команда тепер може знаходити велику кількість «ручок» у будь-якій карті. Це дає змогу паралельно починати розфарбовування в багатьох місцях, що радикально прискорює весь процес.
За словами Томассена, завдяки цьому алгоритм вдалося перевести з квадратичного часу до лінійного. Якщо раніше збільшення кількості регіонів у 10 разів могло уповільнити обчислення приблизно у 100 разів, то тепер розв’язання стає повільнішим лише приблизно у 10 разів.
Від карт до «сиру з дірками»
На перший погляд, удосконалення алгоритму для теоретичної задачі може здаватися далеким від повсякденного життя. Однак дослідники наголошують, що нова ідея має ширше застосування.
Оскільки «ручок» у графах так багато, підхід можна переносити й на інші типи поверхонь, не лише на пласку карту. Торуп зазначає, що це стосується й поверхонь із отворами — наприклад, на кшталт надувного круга чи шматка сиру з дірками. Тобто мова йде про складніші топологічні об’єкти, де також виникають задачі розфарбовування та розбиття на області.
Для більшості людей ці наслідки, ймовірно, залишаться майже непомітними. Але для математиків це перше за 30 років відчутне «полегшення симптомів» їхньої багаторічної «хвороби».
Чому ж Торуп і його колеги витратили десятиліття на теорему, чиї найближчі прикладні асоціації — це хіба що «сир»? Сам учений пояснює це просто: математики трохи божевільні й часто працюють над дуже «занудними» питаннями. Такі задачі кидають виклик людському інтелекту, а розв’язавши одну з них, можна відкрити шлях до відповідей і на інші математичні загадки.
Математики прискорили розв’язання задачі про чотири кольори з’явилася спочатку на Цікавості.

2915