Розділи
Матеріали

Не могли вирішити майже 200 років: математики розібралися з "проблемою чотирьох кольорів"

Тая Кітова
Математики знайшли простіше рішення теореми про проблему чотирьох кольорів | Фото: wikipedia

Теорема, відома як "проблема чотирьох кольорів", не дає вченим спокою з 1852 року. Але тепер, схоже, математикам вдалося зробити прорив.

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

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

Зазначимо, що суть проблеми чотирьох кольорів оманливо проста: у 1852 році англійський математик Френсіс Гатрі припустив, що для розфарбовування будь-якої карти, розділеної на області, достатньо всього чотирьох кольорів — так, щоб сусідні області були пофарбовані в різні кольори. Перший доказ було запропоновано в 1879 році, і він здавався правильним протягом 11 років — втім, пізніше вчені виявили в розрахунках помилку.

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

У 1997 році з’явився більш доступний доказ. Втім, навіть у ньому алгоритмічний метод працював надзвичайно повільно зі зростанням складності карт. Відтоді деякі математики по всьому світу продовжують шукати нові підходи до розв’язання цієї задачі.

На це знадобилися роки, але вчені, схоже, все-таки змогли досягти успіху, виявивши нову деталь, що стосується поверхонь, подібних до карт. Дослідники зрозуміли, що в таких графах міститься набагато більше "наведених конфігурацій", ніж припускали експерти раніше. Це дозволило виділити значно ширший набір вихідних точок для розв’язання задачі.

За словами співавтора дослідження, математика з Данського технічного університету Карстена Томассена, він разом із колегами уявив наведені конфігурації як своєрідні "ручки", за які можна вхопитися, щоб почати розфарбовувати карту в чотири кольори. У результаті їм вдалося довести, що в графах є не одна така "ручка", а величезна кількість. Цікаво, що раніше про це ніхто не знав.

Зазначимо, що виявлення цих "ручок" дозволило розпочати заповнення областей чотирма кольорами одночасно, що експоненціально прискорило весь процес. Автори зазначають, що завдяки цьому новий алгоритм перейшов від квадратичної складності до лінійної.

Інші новини науки