Лэнс Фортноу

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


Скачать книгу

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

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

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

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

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

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

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

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