Лэнс Фотноу - Золотой билет
На самом деле сложности возникают не только у производителей. Допустим, вы решили съездить в «Мир Уолта Диснея» в Орландо во время весенних каникул. Там, естественно, ажиотаж, а вам хочется посетить все самые лучшие аттракционы и при этом не слишком долго стоять в очередях. В неофициальном путеводителе по Диснейленду предлагаются варианты прогулок, призванные помочь вам сократить ожидание; впрочем, авторы путеводителя прекрасно сознают, что поставили перед собой практически неразрешимую задачу.
Однодневная экскурсия по «Волшебному Королевству» для взрослых включает посещение 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 выходит далеко за пределы теоретической информатики, а использование этих загадочных аббревиатур, маскирующих не менее загадочные определения, затрудняет понимание проблемы непосвященными. Как бы то ни было, сейчас уже поздно: за прошедшие десятилетия термин прочно устоялся и заменить его было бы очень непросто даже при наличии достойной альтернативы.
Кнут, конечно, понимал, что если равенство классов докажут, то все его усилия по изобретению названия пропадут даром, поскольку NP-полные задачи «переедут» в класс P. Однако такая перспектива ученого не пугала. «Мне даже хочется, чтобы эта «неприятность» случилась, – пишет он. – Более того, за решение проблемы я объявляю награду: тот, кто первый докажет, что P = NP, получит от меня настоящую живую индейку». Что ж… докажите равенство P и NP – и получите миллион долларов и индейку в придачу!
После Карпа
Работа Карпа послужила толчком к дальнейшему развитию информатики. NP-полные задачи множились, как грибы; профессора и аспиранты по всему миру брались за известные поисковые проблемы (а также находили новые) и доказывали их NP-полноту. В классическом труде 1979 года[3] приводится более трехсот основополагающих NP-полных задач. Число их неудержимо растет; NP-полные задачи возникают не только в информатике и математике, но и в физике, биологии, экономике и во многих других областях. Поиск по Академии Google выдает более 138000 научных статей об NP-полноте за период с 1972 по 2011 год, и в одном только 2011 году на эту тему было создано около 10000 работ. Вряд ли имеет смысл приводить здесь список всех NP-полных задач, однако мне хотелось бы дать вам представление о некоторых из них.
Доминирующее множество
Существует ли в Королевстве группа из 50 человек, в которой у каждого жителя есть хотя бы один друг? NP-полная задача.
Разбиение на треугольники
Комнаты в общежитии Королевского технологического рассчитаны на трех человек. Можно ли расселить студентов таким образом, чтобы в каждой комнате жили только друзья? NP-полная задача.
Гигантские судоку
Судоку – это японская головоломка с числами. В классическом варианте используется квадратная сетка 9 × 9 (рис. 4.2).
Рис. 4.2. Классический вариант судоку
Рис. 4.3. Решение судоку из рис. 4.2
Цель игры – заполнить пустые клетки цифрами от 1 до 9 так, чтобы в каждой строке, каждом столбце и каждом жирно очерченном квадрате 3 × 3 эти цифры не повторялись.
Судоку лежит в классе NP, поскольку проверить имеющееся решение труда не составляет. Вы спросите, насколько сложно это решение найти? На самом деле все не так уж страшно: обычный среднестатистический компьютер при помощи простого перебора с возвратом решает классический вариант всего за несколько секунд.
А как обстоит дело с игрой на большом поле? Например, с сеткой 25 × 25, в которой каждая строка, каждый столбец и каждый мини-квадрат должны содержать все буквы от A до Y?
В этом случае вычисление займет уже гораздо больше времени, а с сеткой 100 × 100 вообще ни один современный компьютер не справится.
