Лэнс Фотноу - Золотой билет

Над решением этих разнообразных задач ученые трудились независимо. Все они потерпели поражение, из-за чего многие склоняются к тому, что 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] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982 / Michael Garey, David Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. – W. H. Freeman, New York, 1979. приводится более трехсот основополагающих 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 эти цифры не повторялись.