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

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

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

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

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

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

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

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

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

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

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

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

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

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

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