Текст книги "Золотой билет. P, NP и границы возможного"

Шесть степеней отчуждения

Выберем наугад двух жителей Королевства; пусть их зовут Элис и Джордж. Маловероятно, что Элис и Джордж дружат. Возможно, между ними существует связующее звено – общий друг Боб. А возможно, и нет. Исследователи Королевского технологического нарисовали схему, в которой каждому жителю Королевства соответствует один элемент; если жители дружат, то соответствующие элементы соединяются на схеме линией. Один из фрагментов схемы выглядел примерно так:

Рис. 3.1. Дружеские связи в Королевстве

Чтобы добраться от Элис до Джорджа, нужно пройти по цепочке из шести связей: Элис дружит с Бобом, Боб – с Кэти, Кэти – с Дэвидом, Дэвид – с Евой, Ева – с Фредом, а Фред – с Джорджем. Исследователи задумались: можно ли любую пару жителей соединить относительно короткой цепочкой дружеских связей? Проявится ли здесь феномен «тесного мира»? Кстати, название феномена пошло вовсе не от аттракциона в Диснейленде, а от слов «мир тесен», которые мы обычно произносим, когда знакомимся с кем-то и выясняем, что нас связывает нечто общее (пусть даже очень отдаленно).

В 1967 году психолог Стэнли Милгрэм поставил свой знаменитый эксперимент по проверке теории «тесного мира». Сначала он выбрал некоего биржевого маклера, проживающего в Бостоне. Имя маклера сохранялось в секрете; для удобства назовем его Том Джонс. Далее совершенно случайным образом в Небраске были выбраны сто держателей акций. Потом – сто людей, не являвшихся акционерами. И, наконец, в Бостоне по объявлению в газетах были найдены еще сто участников. Вторая группа из Небраски и группа из Бостона не имели никакого отношения к инвестиционному миру. Каждому из трехсот участников Милгрэм отослал пакет, в который вложил список инструкций, реестр и пятнадцать почтовых открыток с маркой, адресованных ему в Гарвардский университет. Инструкции выглядели так:

1. Занесите свое имя в реестр.

2. Заполните одну из открыток и бросьте ее в почтовый ящик.

3. Если вы лично знаете бостонского биржевого маклера по имени Том Джонс, перешлите пакет ему.

4. В противном случае выберите среди своих знакомых кого-нибудь, кто, по-вашему, с большей степенью вероятности знает Тома Джонса и чье имя пока не значится в реестре, и перешлите пакет ему (или ей).

Из трехсот участников двести семнадцать переслали пакет своим друзьям. Шестьдесят четыре письма в конце концов добрались до цели, т. е. до Тома Джонса. Средняя длина цепочки оказалась равна 5,2; в результате возникло понятие «шесть степеней отчуждения», означающее, что любых двух человек на планете в среднем разделяет цепочка из шести связей. Отдельные аспекты эксперимента подверглись резкой критике; впрочем, Милгрэм и сам не возводил феномен шести степеней в статус закона, однако его эксперимент показал, что мы связаны гораздо теснее, чем можно было бы ожидать.

Придумывая различные определения понятия связи – более специфические, чем простое знакомство, – можно исследовать и анализировать людские сообщества. Иногда таким образом возникают салонные игры, в которых требуется вычислить расстояние от произвольного человека до некой «центровой» персоны, обладающей, как правило, большим количеством связей. В 1994 году Кевин Бэйкон, выступая в поддержку своего фильма «Дикая река», в шутку заметил, что все актеры в Голливуде снимались либо с ним самим, либо с теми, кто с ним снимался. Тут же родилась игра под названием «Шесть шагов до Кевина Бэйкона», цель которой – найти кратчайший путь между заданным актером и Бэйконом через актеров, с которыми они вместе снимались. Для многих актеров путь до Бэйкона (и, соответственно, друг до друга) оказался очень коротким. Например, Чарли Чаплин находится от Бэйкона всего в трех шагах: в 1967 году он снял фильм «Графиня из Гонконга», в котором сам сыграл второстепенную роль; графиню играла Софи Лорен, которая в 1979 году снялась в малоизвестном фильме «Сила огня»; одну из главных ролей в этом фильме сыграл Илай Уоллак, позднее появившийся в эпизодической роли в фильме «Таинственная река»; в этом же фильме снимался и Бэйкон.

У математиков тоже есть похожая игра: через совместные публикации они ищут расстояние до Пола Эрдёша – гения комбинаторики и рекордсмена по количеству публикаций[2]2
  Мое число Эрдёша равно двум, поскольку у меня имеются совместные публикации с тремя его соавторами. В единицу оно уже вряд ли когда-нибудь превратится: Пал Эрдёш умер в 1996 году. Актерский опыт у меня отсутствует (талант, впрочем, тоже), так что мое число Бэйкона не определено.


[Закрыть].

В Королевском технологическом решили выяснить, выполняется ли закон «шести степеней» для дружеских связей между жителями Королевства. Как проверить, существует ли цепочка из шести связей между Элис и Джорджем? Простейший способ – перебрать все существующие цепочки длины шесть. Вот только в Королевстве, насчитывающем 20000 жителей, таких цепочек может набраться 3198400279980000480000. Даже если предположить, что компьютер будет проверять триллион цепочек в секунду, на решение задачи уйдет более ста лет. Неужели нет способа получше?

Оказывается, есть. Существует совсем не сложная процедура, позволяющая быстро определить расстояние между Элис и Джорджем.

• Присвоим Элис число 0.

• Присвоим всем друзьям Элис число 1.

• Присвоим число 2 всем друзьям тех, кто получил число 1 и у кого пока еще нет числа.

• Присвоим число 3 всем друзьям тех, кто получил число 2 и у кого пока еще нет числа.

• Продолжаем до тех пор, пока Джордж не получит число.

• Число Джорджа и будет расстоянием между ним и Элис.

Подобные неформальные описания вычислительных процессов называются алгоритмами. Своим названием алгоритмы обязаны персидскому математику по имени Мухаммад ибн Муса Аль-Хорезми, жившему в VIII–IX веке н. э. В 825 году Аль-Хорезми написал трактат «Книга об индийском счете», благодаря которому индийская система счисления широко распространилась сначала на Востоке, а затем и в Европе. В латинском переводе книга получила название Algoritmi de numero Indorum. Имя Аль-Хорезми превратилось на латыни в Algoritmi, что в конечном итоге и привело к возникновению термина «алгоритм».

Упомянутый выше алгоритм вычисляет длину пути между Элис и Джорджем приблизительно за полмиллиона шагов. Если мы захотим найти степень отчуждения для всех пар жителей Королевства, нам потребуется средство помощнее: алгоритм Флойда – Уоршелла, который справится с задачей примерно за восемь триллионов шагов. Вам кажется, что триллион – это ужасно много? Но ведь компьютеры и сейчас уже способны выполнять миллиарды операций в секунду, так что мощные институтские процессоры вообще посчитали все за пару минут. В результате выяснилось, что средняя степень отчуждения в Королевстве чуть больше шести. При этом были найдены совершенно изолированные группы друзей, не имеющие дружеских связей с остальными жителями Королевства.

Не стоит недооценивать важность этого события. В институте, конечно, могли бы написать программу, которая методично перебирает все возможные пути, пытаясь найти минимальное количество связей между Элис и Джорджем; вот только этой программе пришлось бы проверить столько путей, что она просто не закончила бы работу за разумное время. Более эффективный алгоритм позволил вычислить степень отчуждения для Элис и Джорджа за ничтожную долю секунды, а для всех пар жителей – за каких-то две минуты.

Задача о числе паросочетаний

В Королевстве заклятых друзей залог счастливых отношений – это прежде всего крепкая дружба. Правда, дружеские связи возникают совершенно бессистемно; хорошо, если вам встретился подходящий партнер, но ведь не всем так везет!

Институтские исследователи вскоре поняли, что их база может принести пользу обществу, и решили с ее помощью повысить число удачных браков. На сайте института появилось объявление о наборе 200 волонтеров: по 100 мужчин и женщин гетеросексуальной ориентации. Волонтеры откликнулись очень быстро. Теперь ученым предстояло «поженить» как можно больше участников.

Сколько вариантов должен рассмотреть каждый участник? Первому мужчине потенциально подходят 100 женщин. Когда выбор сделан, у второго мужчины остается 99 вариантов, у третьего – 98, и так далее. Итого получается 100 умножить на 99 умножить на 98 умножить на… умножить на 2 умножить на 1 – величина, называемая факториалом числа 100 и записываемая в виде «100!». Факториал числа 100 состоит из 158 цифр и намного превосходит гугол – число, изображаемое единицей со ста нулями. Термин «гугол» изобрел девятилетний племянник математика Эдварда Казнера, когда тот попросил мальчика придумать числу название.

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

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

Рис. 3.2. Потенциальные пары в Королевстве

Рис. 3.3. Паросочетания (не максимальное число)

Посмотрим, каким образом можно из друзей составить романтические пары. Начнем с Артура и соединим его с Евой. Боб и Фелисити пока одиноки; соединим их, а также Карла с Гейл. На рис. 3.4 романтические связи обозначены пунктирной линией.

Рис. 3.4. Максимальное число паросочетаний

Теперь у нас не осталось пар друзей, в которых оба были бы свободны. Может, это означает, что мы составили максимальное паросочетание? А вот и нет.

У Дэвида нет пары, однако он дружит с Фелисити, которую мы сочетали с Бобом. Боб дружит с Гейл, но чету они не образуют. Гейл соединена с Карлом, а Карл дружит с одинокой Хелен. Разлучим Боба с Фелисити и Карла с Гейл и составим новые связи. Теперь пара есть у всех!

Вернемся к рис. 3.3. Цепь из чередующихся сплошных и пунктирных линий, первый и последний элемент которой не имеет пары, т. е. не принадлежит паросочетанию, называется увеличивающим путем. При наличии увеличивающего пути мы всегда можем увеличить наше паросочетание. В 1957 году математик Клод Берж показал, что для любого паросочетания, не являющегося максимальным, существует увеличивающий путь. Программисты Королевского технологического реализовали алгоритм нахождения увеличивающих путей, основанный на методе последовательного поиска, и в результате смогли подобрать пару для 98 процентов участников эксперимента.

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

Простыми методами находить увеличивающие пути уже не получалось, и исследователи обратились к трудам Джека Эдмондса. В 1965 году Эдмондс написал работу с изящным названием «Пути, деревья и цветы», в которой представил усложненный алгоритм поиска увеличивающих путей, подходящий для совершенно произвольных схем. Реализовав метод Эдмондса, специалисты института сумели подобрать пару для 97 процентов участников второго эксперимента.

«Пути, деревья и цветы» дали нам не только эффективный способ решения задачи о паросочетаниях для случая произвольной схемы. В группе из 100 человек алгоритм Эдмондса находит максимальное паросочетание примерно за 100⁴, т. е. 100000000 (сто миллионов) шагов, что для современного компьютера сущий пустяк. Методичный перебор всех возможных сочетаний вылился бы примерно в два квинвигинтиллиона шагов, а один квинвигинтиллион – это, между прочим, единица и 78 нулей! В работе Эдмондса есть довольно длинное отступление на тему эффективных алгоритмов. Понимая, что для такого, в сущности, интуитивного понятия, как эффективность, подобрать полноценное формальное определение очень сложно, Эдмондс все-таки предлагает некий критерий. Он называет алгоритм эффективным, если тот находит решение за «алгебраическое» время, т. е. время, «алгебраически» зависящее от размера входных данных. Для 100 человек это может быть, к примеру, 100⁴, 100² или 100¹². В дальнейшем класс задач, для которых существуют такие алгоритмы, получил обозначение «P» – от слова «полиномиальный», заменившего эдмондсовское понятие «алгебраический». Таким образом, класс P представляет собой все многообразие задач, которые можно решить относительно быстро. Ну что ж – в споре «P против NP» мы выслушали мнение первой стороны.

Рис. 3.5. Нетрадиционные потенциальные пары

В поисках клики

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

На деле выяснилось, что труд здесь требуется совершенно непосильный. Количество различных групп размера 50 оказалось непомерно огромным и выражалось числом из 151 цифры; не было и речи о том, чтобы проверить хотя бы сотую долю вариантов. Круг поиска пытались сузить всеми возможными способами – в частности, отсекли тех жителей, у которых было меньше 49 друзей, поскольку они-то уж точно не могли входить в искомую клику. Однако, несмотря на свою высокую квалификацию, исследователи не набрали и 25 друзей и при этом не смогли представить убедительное доказательство того, что клики размера 50 в Королевстве не существует.

Работа встала. Исследователи опустили руки. Внезапно одного из аспирантов осенило: «Слушайте, у нас же есть „Альфа“!» «Альфой» называлось известное, но при этом полусекретное сообщество, все члены которого, по слухам, дружили между собой. Пятьдесят «альфовцев» удалось найти довольно быстро: ведь, в конце концов, секретным сообщество было лишь наполовину. Оставалось только перебрать 1225 пар, чтобы проверить дружеские связи. К изумлению исследователей (но не самих «альфовцев», разумеется), все пятьдесят действительно оказались друзьями. Клика нашлась.

Передай скипетр

Иногда достаточно внести лишь одно незначительное изменение, чтобы задача, решение которой находится очень легко, стала прямо-таки неприступной, и сейчас мы с вами в этом убедимся.

Дети в Королевстве любят играть в игру под названием «Передай скипетр», в которой участники по очереди передают друг другу небольшую палку. Передачей считается тот момент, когда палку держат двое – передающий и принимающий.

Правила игры:

1. Палку можно передавать только друзьям.

2. Между любыми двумя друзьями палка должна переместиться ровно один раз.

Пусть в игре участвуют пятеро детей. Одно из возможных решений таково: начинают с Барбары, она передает палку Эрику, Эрик – Алексу, Алекс – Кэти, Кэти – снова Эрику, а Эрик – Дэвиду.

Рис. 3.6. Дети

Дети, которые играют в «Передай скипетр» часто, вскоре понимают: решение существует, когда нечетное число друзей среди игроков имеется не более чем у двух участников. В данном случае таких участников у нас ровно два – это Дэвид и Барбара, у каждого из которых среди играющих есть только один друг. У остальных детей количество друзей четно: у Алекса и Кэти – по два, у Эрика – четыре. Вы спросите, причем тут четность? А вот причем: чтобы передать кому-то палку, нужно сначала получить ее, поэтому каждый игрок, кроме первого и последнего, обязательно участвует в четном количестве передач.

Рис. 3.7. Дети: число друзей у всех четно

Когда у всех участников число друзей четно, в случае успешного исхода палка возвращается к тому, с кого начали.

В данной ситуации решение может быть таким: начинают с Алекса, он передает палку Эрику, Эрик – Дэвиду, Дэвид – Барбаре, Барбара – снова Эрику, Эрик – Кэти, а Кэти – Алексу.

Прообразом игры «Передай скипетр» послужила одна очень известная головоломка XVIII века. В прусском городе Кёнигсберге (а ныне российском Калининграде) через реку Прегель и ее рукава было перекинуто семь мостов (см. карту на рис. 3.8).

Рис. 3.8. Старинная карта мостов Кёнигсберга

Жителям долгое время не давал покоя вопрос: можно ли посетить все районы города, проходя по каждому мосту ровно один раз? В 1735 году знаменитый математик Леонард Эйлер придумал, как изобразить задачу в виде схемы (см. рис. 3.9).

Рис. 3.9. Схема Эйлера

Очень похоже на игру со скипетром, и критерий существования решения здесь тот же; единственное отличие заключается в том, что узами дружбы связаны уже не дети, а районы города – Северный, Восточный, Южный и Остров. Эйлер доказал, что пройти по каждому мосту ровно один раз невозможно, поскольку во всех районах города количество мостов нечетно.

Так и выяснилось, что задача о семи мостах не имеет решения. В память об этом в игре со скипетром любой подходящий путь (а их бывает несколько) называется эйлеровым. Эйлеров путь можно искать по-разному, в том числе и простым перебором, однако при увеличении количества участников число вариантов заметно возрастает. Дети в Королевстве первым делом пересчитывают игроков с нечетным числом друзей, чтобы понять, существует ли вообще решение; если оно существует, то найти искомый путь уже не составляет особого труда. Поиск эйлерова пути – еще один пример задачи из класса P, т. е. задачи, для которой существует эффективный алгоритм.

Рис. 3.10. Передай скипетр – 2: решение есть

Постепенно дети подрастают. Играть становится все легче и легче; в конце концов «Передай скипетр» надоедает им, и тогда они начинают играть в ее вариацию, которую кто-то, не мудрствуя лукаво, окрестил «Передай скипетр – 2». Правила игры следующие:

1. Палку можно передавать только друзьям.

2. Все игроки, кроме первого, получают палку ровно один раз; в конце палка возвращается к первому игроку.

Для представленной ниже схемы дружеских связей решение может быть таким: Дэвид передает скипетр Барбаре, Барбара – Эрику, Эрик – Алексу, Алекс – Кэти, а Кэти возвращает его Дэвиду.

А вот для следующей схемы решения, как выяснилось, не существует.

Рис. 3.11. Передай скипетр – 2: решения нет

Новые правила выглядят проще. Поначалу детям даже кажется, что вторая игра легче, чем первая, однако при увеличении числа участников играть в нее становится намного сложнее. В 1857 году математик Уильям Роуэн Гамильтон изобрел головоломку «Икосиан», или «Путешествие по додекаэдру», в которой нужно было выполнить обход вершин правильного двенадцатигранника, или додекаэдра.

Рис. 3.12. «Путешествие по додекаэдру»

Эта головоломка – частный случай второй игры со скипетром. Представьте, что вершины додекаэдра соответствуют жителям Королевства, а ребра соединяют друзей, – и получите самую настоящую схему дружеских связей. Сумеете сами обойти додекаэдр и решить вторую игру со скипетром? Ответ вас ждет в конце главы.

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

Рис. 3.13. Додекаэдр

Раскраска домов

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

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

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

Когда в 1852 году английский (а впоследствии южноафриканский) математик Франсис Гатри раскрашивал карту графств Англии, ему пришло в голову, что любую карту можно раскрасить в четыре цвета таким образом, чтобы любые две смежные области получили разные цвета. Его гипотеза широко обсуждалась в математической среде; через некоторое время появились целых два доказательства: первое в 1879 году выдвинул Альфред Кемпе, второе – годом позже – Питер Тэт. Оба были опровергнуты, хотя второе продержалось одиннадцать лет, прежде чем в нем нашлись существенные изъяны. После этого проблема раскраски карт почти сто лет оставалась открытой.

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

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

Неваду окружает кольцо из пяти штатов: Калифорния, Орегон, Айдахо, Юта и Аризона. Пять – число нечетное, поэтому для раскраски штатов кольца потребуется не менее трех цветов. Действительно, предположим, что цветов у нас всего два, к примеру – голубой и зеленый. Покрасим Калифорнию зеленым, соседний с ней Орегон – голубым, Айдахо – зеленым, и Юту – голубым. Осталась Аризона, которая граничит и с зеленой Калифорнией, и с голубой Ютой, так что мы не можем покрасить ее ни в зеленый цвет, ни в голубой. Следовательно, для раскраски всех пяти штатов кольца нужно как минимум три цвета. Пусть Аризона будет желтой.

Рис. 3.14. Невада и ее соседи

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

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

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