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

Чтение книги онлайн.

СКАЧАТЬ времени; к тому же в отсутствие волшебной программы, позволяющей решать сразу все задачи, придется бороться с каждой проблемой отдельно. Однако человеческая изобретательность не знает границ, так что мы в конце концов найдем способ реализовать все свои мечты.

      Глава 3. Классы P и NP

      Заклятые друзья

      Лучший способ получить наглядное представление о классах P и NP – отправиться в воображаемое Королевство заклятых друзей, в котором любые два жителя либо дружат, либо враждуют.

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

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

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

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

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

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

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

      В 1967 году психолог СКАЧАТЬ