Золотой билет - Страница 21

На самом деле сложности возникают не только у производителей. Допустим, вы решили съездить в «Мир Уолта Диснея» в Орландо во время весенних каникул. Там, естественно, ажиотаж, а вам хочется посетить все самые лучшие аттракционы и при этом не слишком долго стоять в очередях. В неофициальном путеводителе по Диснейленду предлагаются варианты прогулок, призванные помочь вам сократить ожидание; впрочем, авторы путеводителя прекрасно сознают, что поставили перед собой практически неразрешимую задачу.

...

Однодневная экскурсия по «Волшебному Королевству» для взрослых включает посещение 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 выходит далеко за пределы теоретической информатики, а использование этих загадочных аббревиатур, маскирующих не менее загадочные определения, затрудняет понимание проблемы непосвященными. Как бы то ни было, сейчас уже поздно: за прошедшие десятилетия термин прочно устоялся и заменить его было бы очень непросто даже при наличии достойной альтернативы.