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

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

Несмотря на вердикт, дело вызвало волну общественного протеста. Неприкосновенность частной жизни находилась под угрозой. Тридцать восемь штатов на законодательном уровне запретили использовать образцы ДНК для каких-либо иных целей, кроме сличения с уже имеющимися в базе CODIS. А губернатор Джорджии в конечном итоге изменил Брауну меру пресечения на пожизненное заключение.

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

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

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

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

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

Трудно представить, что один-единственный алгоритм способен полностью перевернуть нашу жизнь. Неужели все, что можно описать словами, можно и создать? Неужели можно без труда получать практически любые знания? Звучит невероятно, и именно поэтому большинство ученых не верят в равенство P и NP и полагают, что у нас никогда не будет ни урбанского, ни еще какого-нибудь универсального алгоритма.

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

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

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

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

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

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

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

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