Кантор опубликовал некоторые из этих результатов в 1878 году. Он исследовал счетные множества, которые можно поставить во взаимно однозначное соответствие с натуральными числами, и множества, которые взаимно однозначно соответствуют друг другу. Он также понял, что полученное им соответствие между единичным отрезком и единичным квадратом не сохраняет размерности – одно измерение переходит в два, – и, что принципиально важно для нашего рассказа, он подчеркнул, что построенное им соответствие не является непрерывным. То есть точки, расположенные очень близко друг к другу на единичном отрезке, не обязательно соответствуют близко расположенным точкам единичного квадрата.
Идеи Кантора были противоречивы. Некоторые видные математики сочли их чепухой, наверное, потому, что они были слишком оригинальными. Другие, в первую очередь Гильберт, объявили новую область математики, открытую Кантором, настоящим «раем». Полное признание работы Кантора получили только после его смерти.
В 1879 году Ойген Нетто{25} ответил на один очевидный вопрос, доказав отсутствие непрерывного взаимно однозначного соответствия между единичным отрезком и заполненным единичным квадратом. Это сложнее, чем может показаться. Самый значительный прорыв произошел в 1890 году, когда Пеано показал, что наше интуитивное представление о непрерывной кривой может быть обманчивым.
В статье Пеано никаких рисунков нет. Он определяет кривую, записывая координаты точек единичного отрезка в троичной системе счисления, и его построение эквивалентно геометрическому построению на рисунке слева ниже{26}. В 1891 году Гильберт опубликовал еще один пример заполняющей пространство кривой, нарисовав что-то похожее на рисунок справа. Оба построения довольно сложны: на рисунках показана начальная стадия рекурсивного процесса, при котором простые многоугольники раз за разом заменяются более сложными. За прошедшее с тех пор время было найдено много других заполняющих пространство кривых.
Слева: начальный этап геометрической интерпретации заполняющей пространство кривой Пеано. Справа: начальный этап построения заполняющей пространство кривой Гильберта
Заполняющие пространство кривые применяются в компьютерных вычислениях, в частности при хранении и считывании многомерных данных{27}. Базовая идея состоит в том, что мы можем обходить многомерный массив по приближенной заполняющей пространство кривой, упрощая таким образом задачу и сводя ее к одномерному случаю. Еще одно практическое применение – это быстрое и приблизительное решение задачи коммивояжера. Идея заключается в наложении конечной аппроксимации заполняющей пространство кривой на область с городами, определении последовательности городов на кривой, а затем в посещении их в этом порядке, пользуясь на каждом этапе кратчайшим связующим путем. В результате получается маршрут, который обычно не более чем на 25 % превышает по длине оптимальный{28}.
Какие еще фигуры может заполнить кривая? Построение Гильберта можно расширить на три измерения, получив кривую, заполняющую единичный куб, а вообще, кривые могут заполнять гиперкубы любой размерности. Последнее слово в этом вопросе – теорема, которую доказали Ханс Хан и Стефан Мазуркевич. Она полностью характеризует топологические пространства, которые может заполнить кривая{29}. Как оказалось, эти пространства могут быть практически любыми при условии, что они компактны (имеют конечную протяженность) и удовлетворяют нескольким формальным условиям, позволяющим исключить всякие глупости.
Возможно, последнее слово все еще остается за коммивояжером. В 1992 году Санджив Арора и его коллеги{30} обнаружили, что класс сложности NP («легко проверяемые») обладает любопытным свойством, которое ставит под сомнение перспективы нахождения алгоритмов класса P («легко вычислимые»), дающих хорошие приближенные решения. Они доказали, что если P ≠ NP и размер задачи превышает пороговое значение, то вычислить хорошее приближение к ответу не проще, чем найти сам ответ. Единственной альтернативой этому выводу могло бы стать равенство P = NP, что могло бы принести доказавшим миллион долларов, но так и остается гипотезой.
25
E. Netto. «Beitrag zur Mannigfaltigkeitslehre»,
26
H. Sagan. «Some reflections on the emergence of space-filling curves: the way it could have happened and should have happened, but did not happen»,
27
J. Lawder. «The application of space-filling curves to the storage and retrieval of multi-dimensional data», PhD Thesis, Birkbeck College, London (1999).
28
J. Bartholdi. «Some combinatorial applications of spacefilling curves», www2.isye.gatech.edu/~jjb/research/mow/mow.html.
29
H. Hahn. «Über die allgemeinste ebene Punktmenge, die stetiges Bild einer Strecke ist»,
30
Опубликовано в 1998 году: S. Arora, M. Sudan, R. Motwani, C. Lund and M. Szegedy. «Proof verification and the hardness of approximation problems»,