Золотой билет

Победителем конкурса стало название «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 вообще ни один современный компьютер не справится.

Рис. 4.4. Гигантское судоку

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

Есть еще много игр для одного игрока, решение которых представляет собой NP-полную задачу. Возьмем, к примеру, встроенного в Microsoft Windows «Сапера».

Рис. 4.5. «Сапер»