Классы P и NP.

В середине 1960-х формальное определение эффективного алгоритма появилось сразу в двух работах: «Пути, деревья и цветы» Джека Эдмондса и «Внутренняя вычислительная трудность функций» Алана Кобэма.

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

«Необходимо пояснить, что же все-таки понимается под эффективным алгоритмом <…> Я не готов сейчас дать строгое определение и сформулировать какие-то технические требования; вопрос этот находится за рамками данного исследования <…> С практической точки зрения разделять задачи на алгебраические и экспоненциальные гораздо важнее, чем на вычислимые и не вычислимые <…> Введение жесткого критерия могло бы повлечь за собой негативные последствия и помешать развитию алгоритмов, про которые невозможно с уверенностью утверждать, удовлетворяют они данному критерию или нет <…> Важно также понимать, что, принимаясь за поиски хороших, практических алгоритмов, разумно было бы для начала задаться вопросом об их существовании».

Класс алгебраических задач, введенный Эдмондсом, – это и есть класс P: задачи, которые можно решить эффективно. Подчеркивая тот факт, что для постановки вопроса о равенстве P и NP и других подобных задач четкое определение иметь необходимо, ученый в то же время призывает не отказываться от менее формального понятия вычислительной эффективности, и при написании этой книги я старался действовать именно так.

Кобэм в своей работе независимо от Эдмондса вводит тот же класс задач и приводит аналогичные рассуждения о пользе четкого определения.

По ряду причин желание ввести класс P выглядит вполне закономерным. Формализация описания классов вычислительных машин, как правило, приводит нас к четкому определению соответствующих классов функций, так что можно не бояться исказить суть класса P при переходе от интуитивного определения к математическому.

Понятие класса P, так же как и понятие вычислимости, не зависит от конкретной вычислительной модели.

Кобэм тоже считает своим долгом предупредить:

«Этот вопрос напоминает нам о другом, с которым он теснейшим образом связан: о необходимости формализовать понятие эффективности. Впрочем, в данном случае эффективность следует рассматривать под несколько другим углом, поскольку на первый план здесь выходят физические характеристики вычислительного процесса».

Ученый, вероятно, отдавал себе отчет в том, что когда-нибудь появятся вычислительные модели, не укладывающиеся в его классификацию. Понятие эффективности нельзя зафиксировать раз и навсегда, и создание рандомизированных, а затем и квантовых алгоритмов – лишнее тому подтверждение.

В 1971 году Стивен Кук сформулировал понятие класса NP (задачи, решение которых можно эффективно проверить), а также поставил вопрос о равенстве P и NP и нашел первую NP-полную задачу. Годом позже Ричард Карп доказал NP-полноту для целого ряда известных математических проблем.

Выступление Карпа стало самым знаменательным событием на Конференции по вопросам сложности вычислений, проведенной в 1972 году Исследовательским центром IBM имени Томаса Дж. Уотсона. Будущее нового направления активно обсуждалось на итоговом заседании организаторской комиссии. Одной из главных тем был вопрос о том, как из горстки разрозненных результатов – нескольких алгоритмов и нижних оценок сложности – построить единую теорию. Участники заседания, среди которых был и Ричард Карп, вряд ли отдавали себе отчет, что ответ на этот вопрос находится у них перед глазами – в работах Кука и самого Карпа, описывающих классы P и NP, понятие сводимости, а также свойство, которое позже назовут NP-полнотой.

Карп прекрасно понимал, что новой области науки требуется хорошее название:

«Термин „вычислительная сложность“ представляется мне чересчур широким – по крайней мере до тех пор, пока мы не включили сюда работы Блюма и его последователей. „Реальная вычислительная сложность“ подходит больше для какой-нибудь практической, инженерной дисциплины, ну а „сложность компьютерных вычислений“ вообще неверно отражает суть».

В конце концов победило название «вычислительная сложность». Вопрос о равенстве P и NP приобрел огромное значение и быстро затмил все остальные направления исследований в данной области. Абстрактная теория сложности отошла на второй план; даже Блюм переключился на криптографию и верификацию программ. В 1995 году ученый получил премию Тьюринга за свою активную исследовательскую деятельность в 1960–1980-х годах. Когда много лет спустя его спросили, почему он все-таки решил сменить направление, Блюм ответил: «Потому что Кук был прав».