Золотой билет

Я уже смирился с тем, что проблему равенства P и NP ожидает довольно унылая перспектива. Думаю, классы все же не равны – правда, в этой жизни доказательства я уже не увижу. И, думаю, нам не придется жить в совершенном мире из второй главы, хотя полностью исключать такую возможность, конечно, нельзя. Вероятно, пройдет не один десяток (а может, и не одна сотня) лет, прежде чем тайна P и NP будет раскрыта.

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

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

• Большие данные. Каждый день в мире появляются тонны новых данных. Взять хотя бы интернет или многочисленные научные эксперименты… Как работать с такими огромными объемами информации? Как искать, структурировать, анализировать, делать прогнозы?

• Интернет вещей. Почти каждый современный человек пользуется компьютерными сетями – к примеру, общаясь на Facebook или отправляя письмо по электронной почте. Дело идет к тому, что скоро все произведенные человеком предметы, будь то одежда или лампочки для чтения, тоже станут частью сети. Как ориентироваться в мире с таким количеством связей?

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

Параллельные вычисления

В 1965 году Гордон Мур заметил, что число базовых элементов микросхемы – транзисторов – стремительно возрастает с каждым годом. Мур выдвинул смелое предположение: в последующее десятилетие количество транзисторов на одном кристалле каждые два года будет увеличиваться вдвое. Десятью годами дело в результате не ограничилось; закон Мура – так окрестили правило – действует и по сей день, и в ближайшие годы тенденция, похоже, сохранится.

Долгое время закон Мура гарантировал также повышение скорости. Однако примерно к 2005 году на сцену выступили некоторые физические ограничения. Дальнейшее ускорение представлялось нецелесообразным, так как возросшие энергозатраты перевешивали все преимущества быстрых процессоров. Для оптимизации потребления энергии процессоры пришлось даже немного замедлить.

И все же транзисторов на кристалле становится все больше и больше. Зачем это нужно? Чтобы запускать сразу несколько вычислений одновременно: распараллеливая работу, мы значительно уменьшаем время решения задач.

Возьмем для примера суперкомпьютер IBM по имени Уотсон, который в феврале 2011 победил в американской телевикторине «Jeopardy!». Уотсон состоит из 90 серверов IBM Power 750 по 4 процессора Power 7 в каждом. Один процессор Power 7 содержит восемь более мелких процессоров, или ядер, и может параллельно вести сразу восемь вычислений. В итоге получается 32 ядра в одном сервере и 2880 во всем компьютере, так что Уотсон может запускать 2880 процессов одновременно. Неудивительно, что он анализирует варианты ответа быстрее, чем соперники, и успевает нажать кнопку миллисекундой раньше! Впрочем, если производительность компьютеров продолжит расти по закону Мура, то уже через несколько лет 2880 параллельных процессов покажутся нам сущим пустяком; в ближайшие десятилетия могут появиться компьютеры с миллионами и даже миллиардами ядер.

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

К проблеме равенства P и NP тоже пытались применить распараллеливание. Помните Веруку Солт? Девочку из книги «Чарли и шоколадная фабрика», о которой мы говорили в первой главе? Верука очень хотела найти золотой билет, а все билеты были спрятаны в шоколадных плитках. Ее отец – владелец ореховой фабрики – распараллелил задачу, разделив шоколадки между всеми своими рабочими, которых у него было более ста. Так почему бы не сделать то же самое с задачами из класса NP? Например, распределить все потенциальные клики между разными ядрами и даже компьютерами? Иногда время перебора действительно может заметно сократиться – например, с нескольких недель до нескольких часов, однако некоторые NP-задачи и после распараллеливания останутся такими же неприступными. Будь у нас даже миллион компьютеров с триллионом ядер, каждое из которых выполняет квинтиллион операций в секунду, – для поиска клики размера 50 среди 20000 жителей Королевства все равно потребовалось бы в гугол раз больше лет, чем живет наша вселенная (а гугол, как уже говорилось, – это единица и сто нулей). В мире, где можно распараллелить любой процесс, вопрос о равенстве P и NP по-прежнему актуален.

А как обстоит дело с задачами из P? С теми, которые можно решить эффективно? Сумеем ли мы в полной мере воспользоваться всеми преимуществами распараллеливания? Как правило, эффективные алгоритмы действительно удается модифицировать, идет ли речь о простых арифметических задачах или о поиске кратчайшего пути и максимального числа паросочетаний; для всех этих задач вычисления с успехом распределяются по большому количеству ядер.

Класс задач, которые можно быстро решить в параллельном режиме, тоже получил обозначение: его назвали NC, или Nick’s Class, – в честь пионера параллелизации алгоритмов Николаса Пиппенджера. Если P = NP (так ли это, мы пока не знаем), то задачи, для которых существует эффективный алгоритм, в параллельном режиме решаются в разы быстрее. А если NP = NC (что, опять-таки, пока находится под большим вопросом), то и любую переборную задачу из NP тоже можно решить практически мгновенно, распараллелив вычисления по разным машинам и ядрам, – т. е. мир, где NP = NC, еще более совершенен, чем тот, где P = NP. И хотя классы NC и NP вряд ли окажутся равны, отношения между ними не менее загадочны, чем отношения между P и NP.

Большие данные

Каждую секунду мы загружаем 35 минут видеоматериала на YouTube, создаем 1600 сообщений в Twitter, 11000 постов в Facebook, 50000 поисковых запросов в Google и отправляем 3000000 электронных писем (из которых 90 процентов – это спам).

Телескоп «Хаббл» вращается на околоземной орбите и фотографирует космос, отсылая на Землю 200000 байт информации в секунду (один байт – это примерно один символ алфавита). На смену «Хабблу» планируется запустить «Джеймс Уэбб» с огромным параболическим зеркалом, который будет отправлять уже 3500000 байт в секунду.

Большой адронный коллайдер – самый крупный ускоритель частиц на планете – разместился близ границы Швейцарии и Франции. Каждую секунду он создает примерно полмиллиарда байт информации – и так изо дня в день, из года в год, а в году, между прочим, 31 миллион секунд!

Коллайдер построили в Европейском центре ядерных исследований (ЦЕРН). В пару к нему была создана сверхмощная вычислительная сеть, которая распределяет потоки генерируемых коллайдром данных по серверам в тридцати четырех странах; обработкой и анализом этих данных занимаются ученые по всему миру.

Описание ДНК человека занимает примерно 55 миллионов байт. Для хранения ДНК всех жителей Земли, т. е. семи миллиардов человек, потребуется что-то около 400 квадриллионов байт. А если считать не только людей?

Мы умеем быстро и довольно дешево создавать самые разнообразные датчики, которые могут измерить все, что угодно, – температуру, звук, движение, уровень радиации. Каждый датчик постоянно генерирует какую-то информацию, а в одной системе их может быть несколько тысяч – как в американской армии, которая буквально «тонет в датчиках и захлебывается мощными потоками данных».

Информация не всегда приходит из внешнего мира. Научные эксперименты часто оказываются слишком сложными и дорогими, и для понимания физических, биологических и химических процессов активно используется компьютерное моделирование. Результат – очередные колоссальные объемы данных, которые ждут не дождутся, когда их проанализируют.

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

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

Впрочем, иногда большие данные – это не катастрофа, а благо, и в особенности если речь идет о машинном обучении. Алгоритмы тренируются, получая на вход различные выборки данных; чем больше информации, тем умнее станет алгоритм. В распоряжении Google имеется колоссальное число обучающих примеров, и поэтому он так хорошо отсеивает спам, распознает голоса и переводит тексты.

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

Интернет вещей

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

Что будет, если начать подключать к интернету и вещи? Уже совсем скоро в продаже появятся недорогие и компактные чипы, способные выходить в интернет через Wi-Fi и сотовые сети или другие беспроводные системы, которые пока находятся на стадии разработки. Такой чип мы сможем поставить почти на любой предмет, будь то одежда, деталь автомобиля или еда из супермаркета. Под нашим контролем окажется практически все: мы будем знать, когда наши дети не пристегнуты, и без всяких расчетов получим количество съеденных за день калорий. Кончается молоко или шампунь? Беспокоиться не о чем – новую партию доставят автоматически; наверняка она уже на пути к вашему дому. С приемом лекарств больше не будет случаться никаких накладок. Одежда, которую вы надеваете, предупредит вас, если для данной погоды и мероприятия она не годится, а может, даже спросит что-то вроде: «Вы уверены, что хотите надеть с этими брюками именно эту рубашку?» Если вы плохо различаете цвета или совсем не разбираетесь в моде, такая помощь может оказаться очень кстати.

А еще вы больше никогда не потеряете бумажник, ключи, билеты и… что вы там обычно теряете? Честно говоря, у вас вообще не будет никакого бумажника, ключей и билетов. Представьте: двери открываются сами – по сигналу, который отправляет ваш мобильник. Банкомат выдает купюры без лишних вопросов. В супермаркете можно просто взять товар и спокойно уйти. Все счета и налоги оплачиваются автоматически.

Разумеется, все эти устройства должны работать согласованно. Потребуются технологии, при помощи которых вещи смогут общаться, не раскрывая наши персональные данные. Скоординированность процессов достигнет небывалого уровня; подумать только, как улучшится ситуация на дорогах, когда автомобили начнут «разговаривать» друг с другом! Трудоемкие задачи пойдут непрерывным потоком, и справляться с ними нужно будет максимально быстро и корректно: ведь если система не среагирует вовремя, даже мелкая авария может вылиться в огромную пробку. Периодически мы будем упираться в проблему 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 тесно связана с вопросами о разного рода ограничениях; тут и природные ресурсы, и законы развития физических и биологических систем, и даже возможности человеческого мозга. Тайна не раскрыта – а значит, своих пределов мы пока не знаем. И поэтому у нас есть полная свобода действий!