В середине 1960-х формальное определение эффективного алгоритма появилось сразу в двух работах: «Пути, деревья и цветы» Джека Эдмондса и «Внутренняя вычислительная трудность функций» Алана Кобэма.
Работа Эдмондса получила широкую известность благодаря тому, что в ней впервые был предложен эффективный алгоритм для задачи о числе паросочетаний, рассмотренной нами в третьей главе. В главе под названием «Отступление» ученый рассуждает об экспоненциальной и алгебраической сложности, предостерегая в то же время от использования слишком жестких критериев эффективности.
«Необходимо пояснить, что же все-таки понимается под эффективным алгоритмом Я не готов сейчас дать строгое определение и сформулировать какие-то технические требования; вопрос этот находится за рамками данного исследования С практической точки зрения разделять задачи на алгебраические и экспоненциальные гораздо важнее, чем на вычислимые и не вычислимые Введение жесткого критерия могло бы повлечь за собой негативные последствия и помешать развитию алгоритмов, про которые невозможно с уверенностью утверждать, удовлетворяют они данному критерию или нет Важно также понимать, что, принимаясь за поиски хороших, практических алгоритмов, разумно было бы для начала задаться вопросом об их существовании».
Класс алгебраических задач, введенный Эдмондсом, – это и есть класс P: задачи, которые можно решить эффективно. Подчеркивая тот факт, что для постановки вопроса о равенстве P и NP и других подобных задач четкое определение иметь необходимо, ученый в то же время призывает не отказываться от менее формального понятия вычислительной эффективности, и при написании этой книги я старался действовать именно так.
Кобэм в своей работе независимо от Эдмондса вводит тот же класс задач и приводит аналогичные рассуждения о пользе четкого определения.
По ряду причин желание ввести класс P выглядит вполне закономерным. Формализация описания классов вычислительных машин, как правило, приводит нас к четкому определению соответствующих классов функций, так что можно не бояться исказить суть класса P при переходе от интуитивного определения к математическому.
Понятие класса P, так же как и понятие вычислимости, не зависит от конкретной вычислительной модели.
Кобэм тоже считает своим долгом предупредить:
«Этот вопрос напоминает нам о другом, с которым он теснейшим образом связан: о необходимости формализовать понятие эффективности. Впрочем, в данном случае эффективность следует рассматривать под несколько другим углом, поскольку на первый план здесь выходят физические характеристики вычислительного процесса».
Ученый, вероятно, отдавал себе отчет в том, что когда-нибудь появятся вычислительные модели, не укладывающиеся в его классификацию. Понятие эффективности нельзя зафиксировать раз и навсегда, и создание рандомизированных, а затем и квантовых алгоритмов – лишнее тому подтверждение.
В 1971 году Стивен Кук сформулировал понятие класса NP (задачи, решение которых можно эффективно проверить), а также поставил вопрос о равенстве P и NP и нашел первую NP-полную задачу. Годом позже Ричард Карп доказал NP-полноту для целого ряда известных математических проблем.
Выступление Карпа стало самым знаменательным событием на Конференции по вопросам сложности вычислений, проведенной в 1972 году Исследовательским центром IBM имени Томаса Дж. Уотсона. Будущее нового направления активно обсуждалось на итоговом заседании организаторской комиссии. Одной из главных тем был вопрос о том, как из горстки разрозненных результатов – нескольких алгоритмов и нижних оценок сложности – построить единую теорию. Участники заседания, среди которых был и Ричард Карп, вряд ли отдавали себе отчет, что ответ на этот вопрос находится у них перед глазами – в работах Кука и самого Карпа, описывающих классы P и NP, понятие сводимости, а также свойство, которое позже назовут NP-полнотой.
Карп прекрасно понимал, что новой области науки требуется хорошее название:
«Термин „вычислительная сложность“ представляется мне чересчур широким – по крайней мере до тех пор, пока мы не включили сюда работы Блюма и его последователей. „Реальная вычислительная сложность“ подходит больше для какой-нибудь практической, инженерной дисциплины, ну а „сложность компьютерных вычислений“ вообще неверно отражает суть».
В конце концов победило название «вычислительная сложность». Вопрос о равенстве P и NP приобрел огромное значение и быстро затмил все остальные направления исследований в данной области. Абстрактная теория сложности отошла на второй план; даже Блюм переключился на криптографию и верификацию программ. В 1995 году ученый получил премию Тьюринга за свою активную исследовательскую деятельность в 1960–1980-х годах. Когда много лет спустя его спросили, почему он все-таки решил сменить направление, Блюм ответил: «Потому что Кук был прав».
На Востоке
В СССР проблемами теоретической кибернетики занимались многие выдающиеся ученые. Мы подробно остановимся на трех из них; все они являются представителями различных подходов к методу перебора.
1. Сергей Всеволодович Яблонский первым применил перебор для поиска минимальных схем, реализующих дискретные функции. К сожалению, его самонадеянность в сочетании с огромным влиянием, которое он приобрел в научной среде, тормозили развитие теории вычислительной сложности.
2. Андрей Николаевич Колмогоров – крупнейший ученый в истории русской науки – предложил в качестве меры сложности алгоритмическую информацию.
3. Ученик Колмогорова Леонид Анатольевич Левин независимо от Кука сформулировал проблему равенства классов P и NP и пришел к понятию NP-полноты. На родине защитить диссертацию он не смог по политическим причинам.
Сергей Всеволодович Яблонский
В Советском Союзе исследования в области теории вычислений проводились в рамках теоретической кибернетики. Активное развитие этой области началось в 1950-х годах, когда электронные вычислительные машины были взяты на вооружение военными. Сергей Яблонский родился в 1924 году в Москве. Вернувшись с фронта после окончания Второй мировой войны, он продолжил изучать математику в Московском государственном университете. В 1953 году Яблонский защитил кандидатскую диссертацию под руководством Петра Сергеевича Новикова, который одним из первых в СССР начал заниматься проблемами вычислимости. Вместе с Алексеем Андреевичем Ляпуновым, также работавшим под руководством Новикова, Яблонский проводил в МГУ семинары по вопросам реализации булевых функций. Яблонский и Ляпунов организовывали и направляли всю исследовательскую деятельность в области теории вычислений.
Проблема выполнимости, упомянутая в четвертой главе, касается логических формул, т. е. формул, в которых основными операциями являются «И», «ИЛИ» и «НЕ». На самом деле любой вычислительный процесс можно представить в виде набора таких операций, или, другими словами, в виде схемы из элементов «И», «ИЛИ» и «НЕ». Одни задачи решаются схемами небольшого размера, для других необходимо огромное число элементов. Возникает понятие схемной сложности, и в начале пятидесятых Яблонский этим понятием заинтересовался.
