Вольфганг Хакен

Человек, дважды взявшийся за задачу, которую все считали неподъёмной, и дважды доведший дело до конца, — при том что оба раза решение состояло в организации перебора.

Берлин, Киль, Мюнхен

Родился в 1928 году в Берлине. Школьные годы пришлись на войну; в 1946-м он поступил в Кильский университет, где изучал математику, физику и философию, и защитился в 1953 году по топологии.

Первые годы после защиты он работал не в университете, а инженером-разработчиком в фирме «Сименс» в Мюнхене — занимался микроволновой техникой. Математику вёл параллельно.

Узлы

Задача, которую он решил в 1961 году, формулируется просто: дана замкнутая ломаная в пространстве; определить, можно ли её распутать, не разрезая, в обычную окружность.

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

Из той же работы выросли многообразия Хакена — трёхмерные многообразия, содержащие вложенную несжимаемую поверхность. Для них теория работает особенно хорошо, и Тёрстон доказал свою гипотезу геометризации сначала именно для них.

В 1962 году Хакен приехал в США по приглашению Института перспективных исследований, а с 1965-го работал в Иллинойсском университете в Урбане.

Четыре краски

Гипотезой о четырёх красках он занялся в конце 1960-х, познакомившись с методом разрядки Генриха Хееша. Стало ясно, что задача сводима к конечной проверке, но проверка эта чудовищно велика, и Хееш не смог получить машинного времени.

К 1972 году Хакен нашёл соавтора: Кеннет Аппель с того же факультета умел программировать и, что важнее, был готов вести счёт годами, перестраивая правила по ходу дела.

Работа заняла четыре года. Двадцать первого июня 1976 года они объявили результат: 1936 конфигураций, около 1200 часов машинного времени, гипотеза, простоявшая 124 года, доказана.

Отношение Хакена к возражениям было прагматическим: он полагал, что человеческое доказательство длиной в тысячу страниц проверяется хуже, чем машинное, и что требование «проверяемости человеком» — предрассудок, а не критерий.

Долгая жизнь

В Урбане Хакен проработал до отставки в 1998 году, оставаясь при университете и после. Он возвращался к трёхмерной топологии, разбирал подходы к гипотезе Пуанкаре и продолжал печататься в девяносто лет.

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

Умер в Шампейне в октябре 2022 года, девяноста четырёх лет.