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