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

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

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

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

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

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

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

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

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

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

Інші публікації

У тренді

informnauka

Використання будь-яких матеріалів, що розміщені на сайті, дозволяється за умови посилання на данний сайт.

© Новини зі світу науки - informnauka.com. All Rights Reserved.