Как задача дудлера вызвала споры в математике

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

Загадка цвета, вызвавшая столько проблем: какое наименьшее количество цветов нужно, чтобы раскрасить карту так, чтобы никакие соседние штаты или другие обозначенные области не имели одинаковый оттенок? Вот как это работает. Посмотрите на карту прилегающих территорий США ниже.

Он выглядит немного голым. Чтобы сделать карты более яркими и четко выделить их границы, картографы обычно раскрашивают области следующим образом:

Естественно, мы не хотим, чтобы соседние штаты были одного цвета, потому что это сделало бы границы более запутанными. При этом ограничении мы использовали четыре цвета для заполнения карты выше. Могли бы мы сделать это только с тремя? Могут ли другие карты требовать пять или шесть?

Карта не обязательно должна соответствовать реальной географии — подходит любое разделение плоской поверхности на отдельные области. Вопрос в том, учитывая любой такой карты, какое минимальное количество цветов требуется для заполнения каждой области, чтобы никакие две соседние области не были одного цвета? Некоторые основные правила: каждый регион должен быть непрерывным, поэтому технически Мичиган нарушает установку, потому что озеро Мичиган разделяет штат на две несвязанные части. Чтобы два региона считались соседними, они должны иметь непрерывную границу; касание в одной точке (или дискретном наборе точек) не подходит. Например, Юта и Нью-Мексико славятся только коснуться угла и поэтому не считаются соседями для наших целей.

С установленными правилами вот несколько вопросов с неожиданными ответами. Предположим, я распечатал большой плакат со сложной картой, содержащей несколько тысяч регионов. Сколько времени вам понадобится, чтобы определить, можно ли раскрасить карту двумя цветами? Три цвета? Четыре цвета? Вам не обязательно находить раскраски, просто решите, существует ли раскраска для каждого количества цветов. Любопытно, что хотя эти три задачи кажутся почти идентичными, каждая из них требует совершенно разного количества времени для выполнения. Используя самые известные методы:

• Принятие решения о том, достаточно ли двух цветов, займет около часа. Для этого выберите любой регион и выберите для него цвет, скажем, красный. Это вынуждает всех соседей региона переходить в другой цвет, скажем, в синий. В свою очередь, все их соседи становятся красными и так далее, распространяясь по карте. В конце концов вы либо сталкиваетесь с конфликтом, когда соседние регионы имеют общий цвет, и в этом случае «двухцветного» не существует, либо цвета бесконфликтно распространяются по всей карте, и в этом случае вы нашли допустимую окраску. Предварительный расчет с 3000 областей со скоростью 1 секунда на раскрашивание дает 50 минут потраченного времени.
• Предположим, карту нельзя закрасить только двумя цветами. Решение о том, достаточно ли трех цветов, займет больше времени. Полдень пройдет мимо вас. Недели уходили с календаря, пока вы яростно чертили бесконечные конфигурации в поисках той, которая работает. Чтобы продолжить, вам придется передать текущую задачу своим детям, а они своим детям. Поколения жизней, посвященные ничему, кроме поиска трехцветной раскраски этой карты, не уменьшили бы нагрузки, поскольку солнце неизбежно поглотит Землю через несколько миллиардов лет и положит конец глупым усилиям, оставив нас едва ли ближе к ответу. Трудно определить, имеет ли произвольная карта трехцветную раскраску. Здесь «жесткий» — это технический термин, указывающий на то, что он относится к классу вычислительные проблемы известные своей трудоемкостью, называемой NP-полные задачи. Для задач этого класса мы не знаем более быстрых методов, чем более или менее грубый перебор всех возможных решений. Это пространство поиска растет экспоненциально по мере увеличения размера проблемы. Для небольшой карты с несколькими регионами мы могли бы позволить себе тщательно просмотреть все возможные трехцветные раскраски, пока не найдем подходящую (или не придем к выводу, что ее нет). Но количество способов присвоить три цвета картам с тысячами регионов настолько астрономически, что делает исчерпывающий поиск безнадежным.
• И четыре цвета? Ну, это занимает около одной секунды или времени, которое вам нужно, чтобы сказать «да», потому что каждый карту можно раскрасить четырьмя цветами. Это печально известная и давно обсуждаемая теорема о четырех красках.

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

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

Лихорадочное разочарование якобы закончилось в 1879 году, когда появилось доказательство того, что четырех цветов всегда достаточно. Это было подчеркнуто вторым независимым доказательством год спустя. Когда дело улажено, и похвалы распределены, пленены математики вернулись к своим обычным исследовательским программам. За исключением некоторых. Через одиннадцать лет после публикации первого доказательства, оба доказательства были отменены, и скользкая теорема о четырех красках снова вернула свой статус гипотезе о четырех красках. Однако Перси Хивуд, обнаруживший дыру в первоначальном доказательстве, добился некоторого прогресса, доказав, что пять цветов всегда достаточно для заполнения любой карты. Это поставило мир математики в довольно затруднительное положение. Такая, казалось бы, простая задача имела один из двух ответов — четыре или пять, — но никто не знал, какой именно. Так он простоит еще почти столетие.

Никто не мог найти карту, требующую пяти цветов, но полностью исключить возможность одного из них было трудно. Поскольку существует бесконечное количество карт, невозможно проверить каждую из них по отдельности. Ключевой метод решения заключался в сведении задачи к конечному набору случаев, которые мог проверяться индивидуально. Скачок от бесконечности к конечному кажется огромным, но чудовищное количество случаев для проверки по-прежнему намного превышает то, что любой человек может обработать вручную. Поэтому математики Кеннет Аппель и Вольфганг Хакен обратились к смелой идее: вместо этого запрограммировать компьютер для их обработки. В 1976 году, после многих лет тонкой настройки и более тысячи часов компьютерного времени, их алгоритм закончил исчерпывающую проверку каждого случая и была установлена ​​теорема о четырех красках. Это была первая крупная теорема, в доказательстве которой использовался компьютер.

Математический мир в равной степени был охвачен празднованием и тревогой. Один из коллег Аппеля и Хакена, Билл Татт, радовался, что они «Ударь Кракена», в то время как другие презирали мысль о том, что компьютеры покушаются на человеческую изобретательность. Дело также создало философскую проблему в математическом сообществе. Есть ли доказательство, которое не может быть проверено людьми считать доказательством вообще? Многие ожидали, что работа в конечном итоге будет отозвана, как и оба предполагаемых доказательства, которые ей предшествовали. Газета “Нью-Йорк Таймс даже отказался сообщить об объявлении в первую очередь, потому что доказательства теоремы о четырех красках “все равно были фальшивыми».

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

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