Лэнс Фотноу - Золотой билет
А еще вы больше никогда не потеряете бумажник, ключи, билеты и… что вы там обычно теряете? Честно говоря, у вас вообще не будет никакого бумажника, ключей и билетов. Представьте: двери открываются сами – по сигналу, который отправляет ваш мобильник. Банкомат выдает купюры без лишних вопросов. В супермаркете можно просто взять товар и спокойно уйти. Все счета и налоги оплачиваются автоматически.
Разумеется, все эти устройства должны работать согласованно. Потребуются технологии, при помощи которых вещи смогут общаться, не раскрывая наши персональные данные. Скоординированность процессов достигнет небывалого уровня; подумать только, как улучшится ситуация на дорогах, когда автомобили начнут «разговаривать» друг с другом! Трудоемкие задачи пойдут непрерывным потоком, и справляться с ними нужно будет максимально быстро и корректно: ведь если система не среагирует вовремя, даже мелкая авария может вылиться в огромную пробку. Периодически мы будем упираться в проблему P и NP, и тогда придется мобилизовать все наши силы и возможности.
В девяностых годах у компании Sun Microsystems (позднее поглощенной компанией Oracle) появился такой лозунг: «Сеть – это компьютер». Каждый компьютер сети работает самостоятельно, однако вместе они образуют единый вычислительный организм. Интернет вещей – это тоже один (чудовищно огромный) компьютер. Его трудно «приручить», но если мы все-таки справимся, перед нами откроются поистине удивительные возможности.
На пути научно-технического прогресса
Параллельные вычисления, большие данные и интернет вещей не относятся к области научной фантастики. Скорее, это признаки глобальных перемен – перемен, которые уже начались и в ближайшие десятилетия охватят все аспекты нашей жизни. Но куда же они нас заведут?
Никогда не знаешь, каких последствий ждать от внедрения инновационных технологий. В пятидесятые годы прошлого века владелец крупной компании по перевозке грузов Малькольм Маклин придумал специальный транспортный контейнер, который можно было без разгрузки сразу перемещать с корабля на автомобиль. Его открытие вызвало настоящую «контейнерную революцию»; появились специальные судна-контейнеровозы, вмещавшие тысячи контейнеров, а порты массово увольняли грузчиков и переходили на автоматический режим. Экономика Китая резко пошла вверх, поскольку китайские товары можно было дешево доставить в любую точку мира… и все это благодаря какому-то стальному ящику!
Изобретение автомобиля повлекло за собой бурное развитие пригородов. Мобильные телефоны избавили нас от необходимости обо всем договариваться заранее. При помощи Twitter иногда удается свергнуть правительство. Любое нововведение отражается на нас самым непредсказуемым образом; будьте готовы к тому, что это случится снова.
Помимо решения вычислительных задач нам обязательно придется учитывать и человеческий фактор. Люди будут заниматься вредительством – кто нечаянно, по ошибке, а кто вполне осознанно. Возникнет необходимость в надежных и быстро обучаемых интуитивных алгоритмах, способных определить, выполняет ли устройство волю своего «хозяина».
Время от времени кто-то будет пытаться взять под контроль те или иные технологии – в стремлении увеличить свой доход или получить доступ к секретным личным данным. Хуже всего, когда технологии начинают применяться в разрушительных целях; иногда это причиняет лишь мелкие неудобства, однако зачастую обходится крайне дорого и может привести к человеческим жертвам. Для защиты от подобных социальных катастроф потребуются надежные криптосистемы, забота о безопасности и постоянный контроль.
Технология, проработавшая без сбоев долгое время, становится потенциально опасной. Мы начинаем слишком доверять ей, и нам кажется, будто все и дальше будет так же хорошо. Неприятности обычно застают нас врасплох; чем реже они случаются, тем меньше мы оказываемся готовы к ним. Ярчайшие примеры – разрушенные ураганом «Катрина» дамбы в Нью-Орлеане, обширный разлив нефти в Мексиканском заливе после взрыва буровой платформы в 2010 году, а также авария на японской АЭС «Фукусима-1» в 2011 году, спровоцированная землетрясением и последовавшим за ним цунами. С технологией следует обращаться как с диким животным. Следующая крупная авария не должна привести к глобальной катастрофе (впрочем, будем надеяться, что она не случится).
И снова про P и NP
Доказать неравенство P и NP будет очень и очень непросто. Ведь для этого придется обосновать тот факт, что с задачей о клике (или с любой другой NP-полной задачей) не справится ни один известный – а также неизвестный – эффективный алгоритм. Но как можно рассуждать о неизвестных алгоритмах?
Впрочем, я почти уверен, что неравенство классов докажут. Произойдет это нескоро – лет через двадцать, а может, через два столетия или даже два тысячелетия, однако в конце концов мы все же разработаем методы, которые позволят доказать, что P и NP не равны. Математики придут в настоящий экстаз и наперебой заговорят о «великом решении великой проблемы». Новые техники подведут нас к самой сути эффективных вычислений, а они со временем проникнут во все сферы нашей жизни.
«P против NP» – не просто математическая головоломка; это образ мыслей, при котором вычислительные проблемы классифицируются в зависимости от трудоемкости. И хотя формально неравенство классов пока не доказано, при встрече с очередной NP-полной задачей мы не мечтаем отыскать хороший, стопроцентно эффективный алгоритм; мы просто делаем все возможное и применяем весь доступный арсенал, сочетая приближенные методы с эвристическими и повышая вычислительную мощь. NP-полные задачи дают нам ориентиры и побуждают создавать новые способы борьбы.
Классам P и NP удалось сплотить научное сообщество. NP-полные задачи возникают в физике, биологии, экономике и многих других областях. Проблемы у физиков и экономистов как будто совершенно разные, однако благодаря их общности ученые с успехом применяют к ним одни и те же техники и алгоритмы. Метод поиска состояния минимальной энергии физической системы может пригодиться для поиска состояния равновесия в сложных экономических процессах.
Неприступность NP-задач способствует развитию новых технологий. Проблема «P против NP» послужила криптографам музой и перевела искусство шифрования в разряд науки. Необходимость решать задачи из класса NP подтолкнула нас к созданию быстрых и мощных вычислительных систем и заставила разрабатывать теорию квантовых вычислений и другие направления, находившиеся в совершенно зачаточном состоянии.
Вычисление – это нетривиальный процесс, и касается он не одних лишь компьютеров. Проблема равенства P и NP тесно связана с вопросами о разного рода ограничениях; тут и природные ресурсы, и законы развития физических и биологических систем, и даже возможности человеческого мозга. Тайна не раскрыта – а значит, своих пределов мы пока не знаем. И поэтому у нас есть полная свобода действий!
Благодарности
Прежде всего я хотел бы поблагодарить Моше Варди, который вдохновил меня на написание обзорной статьи для журнала Communications of the ACM и сам ее отредактировал. Статья вышла под названием The Status of the P versus NP Problem; ее популярность навела меня на мысль развить тему и выпустить книгу, доступную для широкой аудитории.
Пока я занимался книгой, Уильям Гасарч, с которым мы вместе ведем блог, всячески меня поддерживал и читал каждую главу еще в самом черновом и притом рукописном варианте. Помимо Уильяма предварительную версию всей книги изучили Алана Лидовер, а также Джон, Джим и Крис Пуртило, которые высказали много ценных замечаний. Черновики отдельных глав проверяли Куан-Линг Чен, Джош Грочоу, Ральф Хансен, Адам Калинич, Дэвид Пеннок и Рахул Сантанам; их советы также очень помогли мне.
Мануэль Блюм, Стивен Кук, Дэвид Джонсон, Леонид Левин, Альберт Мейер поделились со мной своими мнением относительно зарождения проблемы равенства P и NP. Благодаря Александру Разборову я немного разобрался с советской историей.
Вся моя научная деятельность в области теоретической информатики, все мое рабочее окружение – исследователи, студенты и многие другие (привести здесь полный список не представляется возможным) – в той или иной мере повлияли на написание этой книги. Особую признательность хочу выразить моим коллегам из Калифорнийского университета в Беркли, Массачусетского технологического института, Чикагского университета, Центра математики и информатики в Амстердаме, научно-исследовательского института NEC, Технологического института Toyota в Чикаго и Северо-Западного университета: я очень ценю нашу дружбу и наши интересные беседы.
