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

Что же может послужить очередным толчком в развитии вычислений? Какие еще грандиозные вычислительные задачи требуют нашего внимания? Читайте дальше – и вы все узнаете.

Я уже смирился с тем, что проблему равенства 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 процентов – это спам).