"Золотой билет" - великолепное введение в P/NP-проблему, в котором описаны история этой задачи и ее влияние на нашу жизнь. В этой информативной и занимательной книге Лэнс Фортноу прослеживает работу, которая велась над задачей во времена холодной войны по обе стороны "железного занавеса", и приводит примеры ее возникновения во множестве дисциплин, включая экономику, физику и биологию.
Для студентов и специалистов в области теории вычислений, всех, интересующихся современными проблемами в математике.
Содержание:
Предисловие 1
Золотой билет 1
Глава 2. Совершенный мир 3
Глава 3. Классы P и NP 7
Глава 4. Самые трудные задачи класса NP 12
Глава 5. Хроника предшествующих событий 16
Глава 6. Преодолевая трудности 20
Глава 7. Как доказать, что P ≠ NP 23
Глава 8. Совершенно секретно 26
Глава 9. Его величество квант 30
Глава 10. Будущее вычислений 33
Благодарности 35
Примечания и список литературы 35
Примечания 36
Лэнс Фортноу
Золотой билет. P, NP и границы возможного
Посвящается Марси, Энни и Молли.
Теперь они, может быть, поймут, чем я занимаюсь и почему.
Предисловие
В Америке почти у каждого второго есть смартфон. Этот маленький компьютер давно обогнал своих более крупных собратьев, которые еще каких-то двадцать лет назад считались очень мощными. Компьютеры снабжают нас информацией о мире и не дают в ней потеряться; позволяют выходить на связь почти из любой точки планеты; справляются с неимоверно сложными вычислительными задачами, будь то составление расписаний для загруженных аэропортов или моделирование космических явлений. Компьютеры распознают наши лица и голоса, регистрируют перемещения, определяют предпочтения и советуют книги, музыку и фильмы… не за горами то время, когда они будут сами управлять автомобилем. Похоже, для них в этом мире нет ничего невозможного?
На самом деле пока они могут не все. Из этой книги вы узнаете о вычислительных задачах, которые мы, вероятно, никогда не научимся быстро решать. Виной тому труднейшая математическая проблема с загадочным названием "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-задачи (например, кратчайший маршрут для коммивояжера). А если не равно, то не сможем.
Задача о разбиении
Взгляните на эти тридцать восемь чисел:
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", и любой алгоритм, решающий ее гигантскую версию, способен вычислить практически все, что угодно.
Немного о руках
Наши руки – это самый удивительный механизм на планете. Они хватают, толкают, указывают пальцем. Завязывают шнурки, выпускают из лука стрелу. Играют на фортепьяно, скрипке, демонстрируют фокусы. В совершенстве управляют автомобилем, лодкой, поездом и самолетом. Руки могут поздороваться, а могут выкрутить запястья. Могут погладить с нежностью или больно ударить. Они общаются языком жестов, пишут слова на бумаге, набирают текст на компьютере. Выполняют ювелирную работу часового мастера и справляются с бензопилой. Руки гениев создают великие картины, симфонии, поэмы… Вероятно, все, чего мы достигли, стало возможным именно благодаря рукам.
Кисть руки содержит двадцать семь костей. На ней пять пальцев, включая незаменимый большой. Под эластичной кожей спрятана сложнейшая система мышц, сухожилий и нервов. Волшебный механизм – вот только самостоятельно это чудо природной инженерии функционировать не будет. От головного мозга должны приходить соответствующие инструкции: рука мертвеца не способна двигаться и вообще что-либо делать.
Рука – это "железо", т. е. натуральное аппаратное обеспечение. А значит, для работы ей обязательно нужна программа – сообщение от мозга, объясняющее, как выполнить то или иное задание.
Профессор Йоки Мацуока из Вашингтонского университета – специалист по робототехнике. Под ее руководством группа исследователей разработала так называемую "анатомически правильную" кисть, пальцы которой в точности повторяют движения человеческих. Технически искусственная рука способна творить те же чудеса, что и настоящая, однако на деле под силу ей оказываются лишь самые простые операции. Нелегко создать программу, которая управляла бы всеми функциями кисти; простейшие движения требуют идеальной координации большого числа мышц, и реализующие их алгоритмы далеко не тривиальны.
Впрочем, наш мозг умудряется контролировать руки без особых проблем. По сути мозг представляет собой сверхмощный компьютер, и раз он может объяснить рукам, как завязать шнурки или создать картину, то написать подобную программу теоретически возможно.
Конечно, одно дело знать, что некий алгоритм существует, и совсем другое – найти его. Программы со временем будут становиться все сложнее и сложнее; искусственная рука научится выполнять намного более трудные операции и однажды – как знать! – вполне может даже превзойти человеческую. Очевидно, нас ждет безумно увлекательное путешествие, вот только скорость движения, похоже, будет очень низкой.
Или не очень? Представьте, что для любой поставленной задачи тут же появляется программа со всей необходимой функциональностью. Например, вы загружаете в компьютер ролик, в котором человек завязывает галстук, и через секунду механические руки уже воспроизводят этот процесс. Или подаете на вход полное собрание сочинений Шекспира, а компьютер в ответ сочиняет новую "шекспировскую" пьесу. Представьте: все, что можно описать словами, можно и создать. Реально ли это? Да – но только если P равно NP.
Вот почему проблема равенства P и NP так будоражит умы. Неужели все задачи мы сможем щелкать как орешки? Или над некоторыми все же придется трудиться? Ответа пока нет, хотя на самом деле на "халяву" мало кто надеется. Вряд ли когда-нибудь выяснится, что P = NP; и все же помечтать об идеальном мире бывает очень и очень приятно.
P против NP
Проблема "P против NP" касается не только описанных выше задач, но и тысяч других, схожих с ними по сути. Насколько быстро можно перебрать огромное число потенциальных вариантов? Насколько трудно будет отыскать тот самый золотой билет, т. е. оптимальное решение поставленной задачи?
Впервые проблема равенства классов упоминается еще в 1956 году – в письме, которое один величайший математик XX века, Курт Гёдель, отправил другому величайшему математику XX века, Джону фон Нейману. К сожалению, вплоть до восьмидесятых о письме ничего не было известно, а вот первые официальные публикации появились в начале семидесятых. Авторы – Стивен Кук и Леонид Левин – независимо друг от друга пришли к одному и тому же вопросу, находясь по разные стороны "железного занавеса". Вслед за этим Ричард Карп опубликовал свой знаменитый список из двадцати одной задачи: все они, включая маршрут для коммивояжера и разбиение на группы, были эквивалентны проблеме "P против NP". Постепенно научное сообщество осознало важность поднятых вопросов, и в развитии информатики наступил поворотный момент. Сейчас проблема равенства классов уже стала основополагающей – причем не только в информатике, но также в биологии, медицине, экономике, физике и многих других областях.
Со временем этот вопрос заработал статус одной из самых трудных задач в истории математики. Шумиха вокруг доказательства Великой теоремы Ферма, предложенного в 1994 году Эндрю Уайлсом, побудила Математический институт Клэя организовать нечто вроде конкурса по решению сложнейших открытых математических проблем. В 2000 году институт опубликовал список из семи "задач тысячелетия" и за каждую из них объявил награду в один миллион долларов. Вот они:
1. Гипотеза Берча–Свиннертон–Дайера.
2. Гипотеза Ходжа.
3. Уравнения Навье–Стокса.
4. Проблема равенства P и NP.
5. Гипотеза Пуанкаре.
6. Гипотеза Римана.
7. Теория Янга–Миллса.