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

расходы необходимо было свести к минимуму, и от Мэри требовалось найти оптимальное решение – кратчайший маршрут, проходящий через все сорок восемь столиц. Посидев немного над картой Америки, Мэри набросала на ней план поездки и после некоторых поправок представила его начальству. Маршрут получился довольно симпатичный.

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

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

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

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

Задача о разбиении

Взгляните на эти тридцать восемь чисел:

14175, 15055, 16616, 17495, 18072, 19390, 19731, 22161, 23320, 23717, 26343, 28725, 29127, 32257, 40020, 41867, 43155, 46298, 56734, 57176, 58306, 61848, 65825, 66042, 68634, 69189, 72936, 74287, 74537, 81942, 82027, 82623, 82802, 82988, 90467, 97042, 97507, 99564.

В сумме все они дают ровно 2000000. Попробуйте разбить их на две группы по девятнадцать чисел так, чтобы сумма чисел внутри каждой группы была равна 1000000. Можете свободно пользоваться калькулятором, Excel или даже написать программу. Ответ приводится в конце главы.

Не так-то просто, верно? Ведь для разбиения существует более семнадцати миллиардов вариантов! Современные компьютеры считают очень быстро, и с хорошей программой у вас есть все шансы получить ответ. Ну а что если я предложу вам не тридцать восемь чисел, а три тысячи восемьсот? Или, что еще лучше, тридцать восемь миллионов? Тут уже никакая программа не справится.

Дурацкая, никому не нужная математическая головоломка, скажете вы. А вот и нет! Представьте, что у нас есть хороший алгоритм, который быстро разбивает заданное множество чисел на две группы с равной суммой (когда это разбиение вообще существует). Тогда мы можем применить его не только для решения подобных головоломок, но и вообще любых задач, к примеру – для поиска кратчайшего маршрута коммивояжера. Дурацкая математическая головоломка на самом деле представляет собой аналог проблемы «P против NP», и любой алгоритм, решающий ее гигантскую версию, способен вычислить практически все, что угодно.

Немного о руках

Наши руки – это самый удивительный механизм на планете. Они хватают, толкают, указывают пальцем. Завязывают шнурки, выпускают из лука стрелу. Играют на фортепьяно, скрипке, демонстрируют фокусы. В совершенстве управляют автомобилем, лодкой, поездом и самолетом. Руки могут поздороваться, а могут выкрутить запястья. Могут погладить с нежностью или больно ударить. Они общаются языком жестов, пишут слова на бумаге, набирают текст на компьютере. Выполняют ювелирную работу часового мастера и справляются с бензопилой. Руки гениев создают великие картины, симфонии, поэмы… Вероятно, все, чего мы достигли, стало возможным именно --">