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

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

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

Лэнс Фортноу

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

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

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

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

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

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

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

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

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

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

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

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