Лэнс Фотноу - Золотой билет. P, NP и границы возможного

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

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

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

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

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

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

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

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

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

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

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

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

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