Двадцать плюс одна
Работу Кука оценили, однако ажиотаж вокруг нее поднялся не сразу. В те годы проблема выполнимости интересовала немногих, и никто еще толком не понимал смысл класса NP. Кук даже не придумал ему названия и пользовался выражением "недетерминированное полиномиальное время". Все изменилось, когда вслед за Куком свою работу опубликовал профессор Ричард Карп из Калифорнийского университета в Беркли.
Ознакомившись с результатами Кука, Карп понял, как можно свести проблему выполнимости к задаче о клике. Он разработал несложный метод преобразования логического выражения в схему, похожую на схему дружеских связей, при котором выражение оказывалось выполнимым в том и только в том случае, когда в схеме существовала клика определенного размера. Отсюда следовало, что любой алгоритм решения задачи о клике заодно решает и проблему выполнимости. Кук доказал, что проблема выполнимости является самой трудной в NP; в работе Карпа было показано, что задача о клике не проще и потому тоже является самой трудной. Появление эффективного алгоритма для задачи о клике будет означать, что любую задачу из NP можно решить быстро, и докажет равенство классов P и NP.
Кук свел задачу о клике к проблеме выполнимости, Карп совершил обратный процесс, и в результате оказалось, что с вычислительной точки зрения эти две совершенно непохожие задачи эквивалентны. Проблему выполнимости можно решить быстро тогда и только тогда, когда быстро решается задача о клике, или – что то же самое – когда P равно NP.
Не ограничившись одной лишь задачей о клике, Карп рассмотрел еще девятнадцать важнейших задач и показал, что все они также являются самыми трудными. Среди них – задача о разбиении множества, задача коммивояжера, поиск гамильтонова пути, раскраска карт и поиск максимального разреза. Появление эффективного алгоритма хотя бы для одной даст нам возможность быстро решать их все и докажет равенство P и NP. Если же классы P и NP все-таки не совпадают, то ни одну задачу из списка – а их там двадцать одна, включая выполнимость, – нельзя решить быстро.
Ошибочно было бы полагать, что рассмотренные Карпом задачи надуманы и интересуют только математиков: большинство из них очень даже практические.
Возьмем, к примеру, компанию Coca-Cola. Под этой маркой производится более трех тысяч напитков по всему миру. Установка для розлива напитков способна выдавать сотни различных продуктов. В ее состав входит несколько разливочных машин, каждая из которых выполняет определенную последовательность операций, чтобы смешать ингредиенты. Одна машина может приготовить множество различных напитков. Задача установки – скоординировать работу всех разливочных машин и добиться наивысшей производительности, выдавая максимальное число напитков за минимальное время, т. е. решить проблему распределения подзадач, которая тоже входит в список Карпа и является самой трудной в NP.
Даже небольшое увеличение скорости производства за счет удачного распределения задач принесет компании-производителю миллионы долларов. С момента появления первых цифровых компьютеров ученые и программисты трудятся над созданием наилучших алгоритмов для решения этой проблемы, однако никому еще не удалось придумать такой алгоритм, который всегда выдавал бы на выходе оптимальное распределение. И это неудивительно: ведь Карп показал, что даже частные случаи проблемы распределения задач являются самыми трудными в NP.
На самом деле сложности возникают не только у производителей. Допустим, вы решили съездить в "Мир Уолта Диснея" в Орландо во время весенних каникул. Там, естественно, ажиотаж, а вам хочется посетить все самые лучшие аттракционы и при этом не слишком долго стоять в очередях. В неофициальном путеводителе по Диснейленду предлагаются варианты прогулок, призванные помочь вам сократить ожидание; впрочем, авторы путеводителя прекрасно сознают, что поставили перед собой практически неразрешимую задачу.
Однодневная экскурсия по "Волшебному Королевству" для взрослых включает посещение 21 аттракциона. Обходить их можно разными способами; всего существует… 51090942171709440000 вариантов! Удивительно, правда? Пятьдесят один миллиард миллиардов – это примерно в шесть раз больше, чем количество песчинок на планете. А если задачу немного усложнить и начать учитывать очередь по записи, посещение ресторанов и шоу, вариантов будет еще больше.
Ученые уже давно бьются над подобными проблемами. Каким образом, к примеру, компания по доставке почты должна составлять маршруты для курьеров, чтобы минимизировать суммарную длину пути и сэкономить время и бензин? Вообще задача, в которой требуется с минимальными усилиями посетить как можно больше мест, настолько распространена, что даже получила имя: задача коммивояжера.
Задачу коммивояжера – так же как и проблему оптимального распределения, задачу о клике, задачу о максимальном разрезе и все остальные задачи из списка Карпа – пытались решить очень многие. Фактически все они бились над одним и тем же: ведь из работы Карпа следовало, что если эффективный алгоритм появится хотя бы для одной задачи, то с его помощью можно будет решить и все остальные.
Над решением этих разнообразных задач ученые трудились независимо. Все они потерпели поражение, из-за чего многие склоняются к тому, что P и NP не равны, хотя доказать это никто не может. Ясно лишь, что если эффективный алгоритм все-таки есть, то найти его будет очень и очень непросто. А пока операторы разливочных машин могут с чистой совестью заявить директору, что оптимального способа распределения просто не существует. Да и энтузиастам из Орландо тоже вряд ли удастся просчитать оптимальный маршрут по Диснейленду.
Все практически неразрешимые вычислительные задачи из списка Карпа уже были известны ранее, но Карп одним махом связал их воедино, и с этого момента проблема "P против NP" вышла на первый план.
Каждый год Ассоциация вычислительной техники вручает премию Тьюринга – "компьютерный" аналог Нобелевской премии, названый в честь Алана Тьюринга, который заложил основы теоретической информатики еще в 30-х годах XX века. В 1982 году за формулировку проблемы равенства P и NP премию получил Стивен Кук. Однако P и NP явно требовали большего, и в 1985 году Ричарда Карпа наградили за вклад в теорию алгоритмов, и в особенности – за список NP-полных задач.
Что в имени?
Названия "P" и "NP", которыми мы пользуемся и по сей день, впервые появились в работе Карпа. Однако для самых трудных задач из класса NP термина у него не было. Кук использовал крайне специфичное обозначение, deg({DNF tautologies}), которое расшифровывалось как "с полиномиальным уровнем сложности по отношению к сложности множества тавтологий, записанных в дизъюнктивной нормальной форме". Карп употреблял выражение "полиномиально полные". Оба варианта звучали как-то не очень.
В итоге с этим вопросом разобрался Дональд Кнут, который в 1974 году получил премию Тьюринга за исследования в области информатики и трехтомный (на тот момент) труд "Искусство программирования". В 1973 году, работая над четвертым томом монографии, Кнут в полной мере осознал важность проблемы равенства P и NP и решил взять инициативу на себя. Ученый запустил опрос населения по почте – не электронной, без которой он и сейчас прекрасно обходится. Впрочем, в те времена без электронной почты удавалось прекрасно обходиться всем.
В опросе предлагалось на выбор три названия: "титанические", "сверхтрудные" и "тяжелые", однако ни одно из них не смогло набрать достаточного количества голосов. В ответ люди присылали собственные варианты – от самых наивных вроде "неподдающиеся" или "упрямые" до откровенно насмешливых "не лыком шиты" или "черт ногу сломит".
Победителем конкурса стало название "NP-полные", которое после довольно бурных обсуждений предложили сотрудники Лабораторий Белла в Нью-Джерси. Этот термин, также отсутствовавший в первоначальном списке, обязан своим появлением математической логике, где система фактов, или аксиом, называется полной, если с ее помощью можно обосновать любое истинное высказывание в данной логической теории. Аналогичным образом, задача из класса NP называется NP-полной, если с ее помощью можно решить все остальные NP-задачи.
Кнут принял решение оставить этот вариант, хотя и чувствовал некоторую неудовлетворенность: ему хотелось, чтобы название состояло из одного слова и при этом давало интуитивное представление о трудных переборных задачах, т. е. было доступно самой широкой публике.
В 1974 году, излагая результаты последних исследований, Кнут написал: "Вообще-то термин "NP-полные" кажется мне слишком техническим для широкой аудитории. Зато он по крайней мере адекватный".
Название "NP-полные" очень быстро вошло в стандартную терминологию. А Кнуту потребовалось почти сорок лет, чтобы закончить работу над четвертым томом.
Может, стоило все-таки попытаться придумать менее специфичное название? Причем не только для NP-полных задач, но и для самих классов P и NP? Ведь проблема равенства P и NP выходит далеко за пределы теоретической информатики, а использование этих загадочных аббревиатур, маскирующих не менее загадочные определения, затрудняет понимание проблемы непосвященными. Как бы то ни было, сейчас уже поздно: за прошедшие десятилетия термин прочно устоялся и заменить его было бы очень непросто даже при наличии достойной альтернативы.