Дискретная математика

от кости Ишанго до P vs NP

Сюжет в одном абзаце

Двадцать тысяч лет человек считает предметы, и ещё девятнадцать тысяч из них — без всякой теории: зарубки на кости, треугольник биномиальных коэффициентов в Кайфыне, календарные расчёты в Новгороде, комбинаторика с доказательствами в Провансе. Настоящая дисциплина начинается с задач, которые не лезут ни в один существующий раздел: мосты Кёнигсберга, раскраска карты графств, игра на додекаэдре. Сто лет это коллекция курьёзов; собирает её в науку межвоенная Венгрия — Кёниг пишет первый учебник теории графов, Эрдёш придумывает доказывать существование подбрасыванием монеты. Одновременно Тьюринг определяет, что значит «вычислить», а Шеннон — что значит «информация», и у дискретной математики появляются два измерения, которых не было ни у одного другого раздела. Дальше приходят машины — и с ними вопрос «сколько стоит вычисление». В 1971–1973 годах выясняется, что вековые головоломки — раскраска, гамильтонов цикл, укладка рюкзака — это одна и та же задача, и вопрос о ней входит в список задач тысячелетия нерешённым. А в конце века дискретное «съедает мир»: криптография, поисковики, машинное обучение — всё это конечные структуры и алгоритмы на них.

Что делает эту линию особенной

Первое: у неё нет непрерывности, и это не бедность, а другой предмет. Классическая математика три века строилась вокруг предела: производная, интеграл, ряд. Здесь ничего этого нет — есть конечные множества, графы, слова, алгоритмы. Соответственно другие методы: вместо предельного перехода — подсчёт, индукция, перебор с оценкой; вместо «сколь угодно малого» — «на единицу больше».

Второе: вопрос «сколько стоит» здесь главный. Ни в анализе, ни в алгебре не спрашивают, за сколько шагов получен ответ: важно, что он есть. В дискретной математике существование решения обычно тривиально (переберите все варианты), и вся содержательность — в том, можно ли обойтись без перебора. Из этого выросла теория сложности, и с ней — самая знаменитая открытая задача современности.

Третье: она моложе всех и старше всех сразу. Кость с зарубками — древнейший предмет на карте; а дисциплина с этим именем существует лет девяносто, из них по-настоящему бурно — последние пятьдесят. Разрыв между «люди считают» и «есть наука о счёте» здесь больше, чем где-либо ещё.

Один сквозной сюжет: перебор

Если у линии есть главный герой, то это перебор — и вопрос, можно ли без него обойтись.

Взгляните, как он проходит через всю линию.

Эйлер отказывается перебирать $7!$ маршрутов по мостам и находит критерий, который проверяется взглядом на чертёж. Перебор побеждён.
Гамильтон ставит внешне такую же задачу — обойти вершины вместо рёбер, — и критерия для неё не найдено до сих пор.
Гатри спрашивает про четыре краски; ответ приходит через 124 года и оказывается перебором 1936 случаев, выполненным машиной.
Карацуба показывает, что даже школьное умножение делается быстрее, чем кажется.
Карп и Левин обнаруживают, что все «неподдающиеся» задачи неподдаются одинаково: у них общая структура, и либо перебор устраним сразу во всех, либо ни в одной.

Вопрос $\mathrm{P}$ против $\mathrm{NP}$ — «если решение легко проверить, легко ли его найти?» — прямой потомок вопроса Эйлера о мостах. Только теперь известно, что от ответа зависит устройство цивилизации: вся современная криптография держится на предположении, что перебор устранить нельзя.

Три оговорки, полезные при чтении

Первая: «дискретная математика» — не раздел, а зонтик. Под ним теория графов, комбинаторика, теория алгоритмов и сложности, теория кодирования, криптография, отчасти математическая логика. Объединяет их не предмет, а способ работы: конечные объекты и конструктивные вопросы о них.

Вторая: здесь особенно много переоткрытий и потерянных приоритетов. Треугольник биномиальных коэффициентов открывали по меньшей мере пятеро в трёх культурах; NP-полноту — Кук и Левин независимо; криптографию с открытым ключом — дважды, причём одну из версий засекретили. Причина, кажется, в низком пороге входа: чтобы задать хороший дискретный вопрос, не нужно двадцати лет подготовки, и потому его задают многие.

Третья: это единственная линия карты, где машина — действующее лицо. Не инструмент, а участник: четыре краски доказаны компьютером и человеком целиком не проверены; доказательство проверено другой машиной через двадцать девять лет. Вопрос «что такое доказательство» после 1976 года звучит иначе, чем до.

Открыть на карте

1

Ишанго (оз. Эдуард) ок. 20 000 лет до н. э.
Кость Ишанго
Кость с зарубками, сгруппированными в три столбца, — древнейший предмет на этой карте. Что именно записано, спорят семьдесят лет: от счётной палочки до лунного календаря и простых чисел. Разбор этого спора — хорошее упражнение в том, как отличить закономерность от собственной проекции.
2

Кайфын ок. 1050 г.
Кайфын: треугольник до Паскаля
Цзя Сянь в сунской столице строит таблицу биномиальных коэффициентов и применяет её к извлечению корней. Тот же треугольник независимо знали в Багдаде, в Индии и в Персии; «треугольником Паскаля» он станет через шесть веков.
3

Новгород 1136
Кирик Новгородец: «Учение о числах»
Первый математический текст Руси. Дьякон Антониева монастыря считает, сколько времени прошло от сотворения мира, разбирает пасхальные циклы — и, деля час на всё более мелкие доли, доходит до седьмой дробной части, после чего замечает, что дальше делить нечего.
4

Оранж (Прованс) 1321
Герсонид: комбинаторика с доказательствами
Трактат «Маасе хошев» доказывает формулы для перестановок и сочетаний — систематически, по индукции, за три века до Паскаля. Написанный по-еврейски в Провансе, он остался вне главного русла, и историки переоткрыли его уже в новое время.
5

Париж лето 1654
Лето 1654 года: Паскаль, Ферма и задача о разделе ставки
Комбинаторика и вероятность рождаются сросшимися

Переписка Блеза Паскаля и Пьера Ферма дала общий метод решения задачи о разделе банка в прерванной игре. Главное новшество: справедливую долю игрока определяют не по уже набранным очкам, а по вероятности его будущей победы.
6

Санкт-Петербург 1736
Семь мостов Кёнигсберга
Одна прогулка — два потомка: топология и теория графов

Можно ли пройти по всем семи мостам, не пройдя ни по одному дважды? Эйлер отвечает «нет» и объясняет почему — рассуждением, в котором нет ни одной длины и ни одного угла. Обычно отсюда отсчитывают начало и топологии, и теории графов.
7

Лондон 1852
Четыре краски: 124-летний сериал
Студент, раскрашивая карту английских графств, замечает, что четырёх цветов всегда хватает. Доказательство Кемпе одиннадцать лет считалось верным, потом рухнуло — и из обломков спасли теорему о пяти красках. Настоящая развязка придёт через 124 года и будет машинной.
8

Дублин 1856–1859
Икосианская игра
Гамильтон придумывает головоломку: обойти все вершины додекаэдра по одному разу. Права продаёт издателю за 25 фунтов, игра проваливается. Через 115 лет задача о гамильтоновом цикле окажется среди первых NP-полных — и обнаружится, что от эйлеровой её отделяет пропасть.
9

Кембридж 1930
Рамсей: полный беспорядок невозможен
В любой достаточно большой структуре найдётся большой упорядоченный кусок — как ни старайся его разрушить. Теорема доказана как вспомогательная лемма в работе по логике; автор умер в том же году, двадцати шести лет.
10

Будапешт 1931–1936
Будапешт: дисциплина получает имя
Теорема о паросочетаниях в двудольных графах — и первая в истории монография по теории графов. Столетие разрозненных головоломок кончается: у предмета появляются имя, учебник и метод. Судьба автора трагична: он покончил с собой в октябре 1944 года, за несколько дней до депортаций.
11

Кембридж 1936
Тьюринг: что такое «вычислить»
Дискретная математика получает измерение вычислимости

Чтобы ответить «алгоритма не существует», надо сперва сказать, что такое алгоритм. В 1936 году это сделали трижды и независимо, и все три определения совпали. У Тьюринга определение оказалось не только точным, но и чертежом машины, которой ещё не было.
12

Санкт-Петербург 1939
Канторович: оптимизация раскроя фанеры
Лаборатория фанерного треста спросила, как распределить работу между станками. Ответом оказался новый раздел математики — линейное программирование, а вместе с ним двойственные оценки, которые в СССР пришлось называть словами, не похожими на слово «цены».
13

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

Мюррей-Хилл (Bell Labs) 1948
Шеннон: вероятность становится информацией
Одна статья создаёт теорию информации

Клод Шеннон определяет количество информации через энтропию распределения и доказывает, что у канала связи есть точная пропускная способность. Вероятность из инструмента расчёта шансов превращается в меру незнания.
15

Киев 1948–1951
МЭСМ: первая ЭВМ континентальной Европы
Двенадцать научных сотрудников в бывшем монастырском корпусе под Киевом за три года собрали машину на шести тысячах ламп. У ENIAC людей было раз в десять больше. Всё это происходило, пока в философских журналах кибернетику называли реакционной лженаукой.
16

Москва 1959
«Сетунь»: троичная ЭВМ
Единственная в мире серийная троичная вычислительная машина. У неё цифры не 0 и 1, а −1, 0 и +1, и в такой системе отрицательные числа не требуют знака, а округление — это отбрасывание. Наглядное доказательство, что двоичность — не закон природы, а выбор.
17

Москва 1960
Карацуба: быстрее, чем учили в школе
Колмогоров предположил на семинаре, что умножать быстрее, чем в столбик, невозможно. Двадцатитрёхлетний студент опроверг гипотезу за неделю. Способ, которым он это сделал, оказался первым примером того, что «естественный» алгоритм бывает не лучшим, — и с него началась привычка спрашивать, сколько стоит вычисление.
18

Новосибирск 1960–1975
Канторович в Академгородке
Академгородок — попытка вырастить науку в сосновом лесу, вдали от столиц и, как надеялись, от начальства. Канторович провёл здесь одиннадцать лет, довёл линейное программирование до промышленных расчётов и в 1975 году получил Нобелевскую премию по экономике — единственную у советского учёного.
19

Киев 1962
Глушков: кибернетика и ОГАС
Человек, решивший одну из версий пятой проблемы Гильберта, а потом придумавший алгоритм, который сегодня работает в каждом движке регулярных выражений, — и предложивший связать всю экономику страны в единую сеть вычислительных центров за семь лет до ARPANET. Первое сбылось, второе работает, третье не состоялось.
20

Кембридж (Массачусетс) гипотеза Ван Хао — 1961, диссертация Бергера — 1964, мемуар — 1966
Ван Хао и Бергер: задача домино неразрешима
Задача о плитках: неразрешимость приходит в комбинаторику

Ван Хао свёл кусок логики к задаче о плитках и предположил: если набор замощает плоскость, то замощает и периодически. Его аспирант доказал обратное — построил набор из 20 426 плиток, замощающий плоскость и никогда не повторяющийся, и вывел отсюда, что алгоритма для распознавания замощаемости не существует. Апериодические паркеты родились как побочный продукт теоремы о неразрешимости.
21

Челтнем (GCHQ) 1969–1974
Челтнем: секретная криптография, запрещённый приоритет
В британской службе радиоразведки за пять лет придумали криптографию с открытым ключом целиком: идею, реализацию и обмен ключами. Всё засекретили. Когда через двадцать три года разрешили рассказать, автор идеи не дожил трёх недель.
22

Беркли 1972
NP-полнота: 21 задача — одна проблема
Гамильтонов цикл, раскраска карты, укладка рюкзака, расписание — двадцать одна задача из разных областей оказалась одной задачей в разных костюмах. Быстрый алгоритм для любой из них дал бы быстрый алгоритм для всех. Есть ли он — вопрос, стоящий в списке задач тысячелетия.
23

Москва 1973
Левин: универсальные задачи перебора
Две страницы в «Проблемах передачи информации» — и то же самое, что за океаном заняло две большие статьи. Формулировка при этом другая и, пожалуй, более естественная: не «есть ли решение», а «найдите решение». А в придачу — теорема о том, что оптимальный алгоритм существует всегда.
24

Урбана (Иллинойс) 21 июня 1976
Урбана: четыре краски доказаны машиной
1936 конфигураций, около 1200 часов машинного времени — и гипотеза, простоявшая 124 года, доказана. Вместе с ней пришёл вопрос, которого математика прежде не знала: что считать доказательством, если ни один человек не может его прочитать?
25

Стэнфорд «New Directions in Cryptography» — ноябрь 1976
Диффи и Хеллман: ключ, который можно опубликовать
Общий секрет вырабатывается на глазах у всех

До 1976 года всякий шифр требовал заранее переданного ключа: для тысячи абонентов это полмиллиона мешков с секретами. Диффи и Хеллман показали, как двое вырабатывают общий секрет, обмениваясь числами в открытую. Самой системы шифрования у них не было — только понятие и работающий протокол обмена.
26

Кембридж (Массачусетс) 1977
RSA: теория чисел уходит в каждый смартфон
Малая теорема Ферма в обобщении Эйлера превращается в шифр, у которого ключ шифрования можно публиковать. Харди в 1940 году гордился тем, что теория чисел не имеет применений; через тридцать семь лет она стала инфраструктурой цивилизации.
27

Беркли Миллер — 1976, Соловей и Штрассен — 1977, Рабин — 1980
Соловей и Штрассен: монетка вместо доказательства
Поворот, ради которого стоило разбираться со случайностью: она оказалась не помехой, а ресурсом. Чтобы узнать, простое ли число, делители искать не нужно — достаточно взять наугад свидетеля и проверить одно равенство по модулю. Составное число случайный свидетель уличает с вероятностью не меньше половины, так что двести попыток делают ошибку менее вероятной, чем отказ процессора. Ответ «да» здесь не доказан, а лишь очень вероятен, — и на этом с тех пор держится всякая выдача ключей.
28

Москва 1979
Хачиян: метод эллипсоидов
Четыре страницы в «Докладах Академии наук» закрыли вопрос, который стоял тридцать лет: линейное программирование решается за полиномиальное время. Западная пресса вынесла это на первую полосу, переврав до неузнаваемости. А настоящая ценность метода обнаружилась потом и оказалась не в скорости.
29

Беркли доклады — 1982, журнальные версии — 1984
Блюм, Микали и Яо: подделка, которую не отличить
Настоящей случайности у машины нет: фон Нейман ещё на исходе сороковых назвал состоянием греха попытку получать случайные цифры арифметикой. Ответ, найденный в Беркли: настоящая и не нужна. Достаточно, чтобы короткое случайное зерно разворачивалось в длинную последовательность, которую никакая быстрая программа не отличит от честной монетки, — а это возможно, если существуют задачи, которые легко задать и трудно решить. Случайность впервые определена не через мир и не через описание, а через того, кто смотрит.
30

Мюррей-Хилл (Bell Labs) доклад на симпозиуме FOCS — ноябрь 1994; журнальная версия — 1997
Шор: разложение на множители за полином — но не на этой машине
У всей криптографии появляется срок годности

Разложить число на множители — то же самое, что найти период ряда его степеней, а искать период умеет преобразование Фурье. Питер Шор собрал из этого квантовый алгоритм, которому взлом ключа стоит куба его длины вместо астрономической величины. Машины нужного размера нет и, возможно, не будет — но записанное сегодня можно расшифровать через двадцать лет.
31

Стэнфорд 1996–1998
PageRank: линейная алгебра съедает веб
Двое аспирантов предложили считать важность веб-страницы собственным вектором матрицы гигантского графа ссылок. Математика — теорема Перрона — Фробениуса 1907 года, ждавшая приложения девяносто лет, и цепь Маркова, придуманная для «Евгения Онегина». На этом заканчивается наша линия — и, пожалуй, заканчивается разделение математики на чистую и прикладную.
32

Иерусалим Нисан и Вигдерсон — 1988, Импальяццо и Вигдерсон — 1997
Импальяццо и Вигдерсон: а нужна ли она вообще
Если случайность — это неотличимость для наблюдателя, её можно подделать до конца. Теорема утверждает: стоит существовать хоть одной по-настоящему трудной для схем задаче — и всякий вероятностный алгоритм переделывается в обычный с той же скоростью. Монетка не даёт вычислителю ничего принципиально нового; она удобство, а не сила. Верится в это охотно, но доказать посылку пока не удалось, и «случайность бесполезна для вычислений» остаётся одной из главных открытых задач теории сложности.