Посвящается Марси, Энни и Молли.

Теперь они, может быть, поймут, чем я занимаюсь и почему.

Copyright © 2013 by Princeton University Press Все права защищены. Никакая часть этой книги не может быть воспроизведена или передана в любой форме или любыми средствами, электронными или механическими, включая фотокопирование, запись или использование средств хранения и поиска информации, без письменного разрешения Издателя.

© Лаборатория знаний, 2016

Предисловие

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

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

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

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

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

В 2008 году главный редактор журнала Communications of the ACM Моше Варди предложил мне написать о проблеме статью. Ассоциация вычислительной техники, или ACM, – это крупнейшая международная организация, объединяющая специалистов в области компьютерных наук, а ее главный научный журнал Communications of the ACM публикует статьи на интересующие компьютерное сообщество темы.

Поначалу я пытался «сбагрить» работу кому-то еще, но потом все же сдался. «Вон физики же издают популярные статьи про теорию струн, – убеждал меня Моше. – И не только статьи, а целые книги! Так что, я думаю, у нас тоже получится объяснить всем теорию сложности и ее достижения». Я писал, ориентируясь на читательскую аудиторию журнала; речь в работе шла не столько о текущем статусе проблемы, который можно было бы описать одним словом – «открыта», сколько о методах борьбы с трудоемкими задачами. Статья The Status of the P versus NP Problem вышла в сентябре 2009 года и быстро побила все рекорды по скачиванию за всю историю существования сайта журнала.

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

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

Формальных определений вы здесь не найдете: хороших учебников и сайтов, излагающих математическое описание проблемы и связанные с ней результаты, сейчас и так довольно много. Цель книги – дать представление о том, что могут и чего не могут дать нам вычисления в век, когда мир уже невозможно представить без компьютеров.

Итак, вперед, к классам P и NP!

Лэнс Фортноу

Иванстон, штат Иллинойс

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

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

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

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

«На моей фабрике делают разные штуки из земляных орехов, и работает там около ста женщин, они лущат орехи, перед тем как посолить их и обжарить. Этим-то женщинам я и сказал: „О’кей, девочки, с этой минуты кончайте лущить орехи и начинайте снимать обертки с шоколадок“. И они взялись за дело. Каждая работница моей фабрики с утра до вечера только этим и занималась.

Прошло три дня, а толку никакого. О! Это было ужасно! Моя малышка все больше огорчалась и, когда я приходил домой, каждый раз начинала кричать: „Где мой золотой билет? Хочу золотой билет!“ Она часами валялась на полу, дрыгала ногами и визжала. Я не мог больше смотреть на страдания несчастной крошки и поклялся продолжать поиски, пока не найду то, что она просит. И вдруг… вечером четвертого дня одна из моих работниц закричала: „Я нашла! Золотой билет!“ И я сказал: „Быстро давайте сюда“. Она так и сделала. Я бросился домой и вручил билет Веруке. Теперь она улыбается, и мы снова счастливы».

Неважно, каким образом вы будете искать билет: вам, как и мистеру Солту, понадобится много времени и денег – или удача, когда и того, и другого дефицит. Возможно, однажды какой-нибудь умный человек изобретет недорогой прибор для быстрого поиска билетов. А возможно, и нет.

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

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

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

Давайте посмотрим, какая проблема свалилась на Мэри – коммивояжера компании US Gavel Corporation, зарегистрированной в Вашингтоне, округ Колумбия. Директор проучил Мэри объехать столицы всех сорока восьми континентальных штатов и попытаться убедить местные власти вложить средства в его замечательную фирму. Транспортные расходы необходимо было свести к минимуму, и от Мэри требовалось найти оптимальное решение – кратчайший маршрут, проходящий через все сорок восемь столиц. Посидев немного над картой Америки, Мэри набросала на ней план поездки и после некоторых поправок представила его начальству. Маршрут получился довольно симпатичный.

Рис. 1.1. Задача коммивояжера

Однако транспортный отдел попросил ее подумать еще и постараться уложиться в 17000 километров. Мэри написала программу, которая в поисках самого короткого маршрута перебирала все возможные перестановки из сорока восьми городов. Прошла неделя, а программа все работала. Тогда Мэри решила кое-что прикинуть. Первый город можно было выбрать сорока восемью способами. Второй – сорока семью. Третий – сорока шестью, и так далее. Итого потенциальных маршрутов набралось 48 × 47 × 46 × … × 2 × 1. Для записи этого числа требуется 62 цифры. Вот оно: 12413915592536072670862289047373375038521486354677760000000000.

Если мы даже предположим, что один маршрут обрабатывается всего за 0,00000000000000000033 секунды (примерно столько времени требуется свету, чтобы преодолеть дистанцию, равную диаметру самого мелкого атома), то на полную проверку всех маршрутов все равно уйдет в десять тысяч миллиардов триллионов больше лет, чем живет наша вселенная. Понятно, почему Мэри не увидела ответ через неделю! Неужели для поиска оптимального пути – этакого золотого билета среди всех возможных маршрутов-шоколадок – нет способа получше?

Вот мы и подошли к сути дела. Вопрос о равенстве классов P и NP самым непосредственным образом связан с задачей быстрого поиска кратчайшего маршрута коммивояжера (и не только с ней). Названия классов – сокращения от технических терминов, однако будет лучше воспринимать их просто как общие понятия, а не как конкретные математические объекты. Класс NP – это множество задач, которые мы хотим решить; класс P – задачи, которые мы умеем решать быстро. Если P равно NP, мы всегда сможем быстро найти решение любой NP-задачи (например, кратчайший маршрут для коммивояжера). А если не равно, то не сможем.