Золотой билет. 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-х годах. Когда много лет спустя его спросили, почему он все-таки решил сменить направление, Блюм ответил: «Потому что Кук был прав».

В СССР проблемами теоретической кибернетики занимались многие выдающиеся ученые. Мы подробно остановимся на трех из них; все они являются представителями различных подходов к методу перебора.

1. Сергей Всеволодович Яблонский первым применил перебор для поиска минимальных схем, реализующих дискретные функции. К сожалению, его самонадеянность в сочетании с огромным влиянием, которое он приобрел в научной среде, тормозили развитие теории вычислительной сложности.

2. Андрей Николаевич Колмогоров – крупнейший ученый в истории русской науки – предложил в качестве меры сложности алгоритмическую информацию.

3. Ученик Колмогорова Леонид Анатольевич Левин независимо от Кука сформулировал проблему равенства классов P и NP и пришел к понятию NP-полноты. На родине защитить диссертацию он не смог по политическим причинам.

В Советском Союзе исследования в области теории вычислений проводились в рамках теоретической кибернетики. Активное развитие этой области началось в 1950-х годах, когда электронные вычислительные машины были взяты на вооружение военными. Сергей Яблонский родился в 1924 году в Москве. Вернувшись с фронта после окончания Второй мировой войны, он продолжил изучать математику в Московском государственном университете. В 1953 году Яблонский защитил кандидатскую диссертацию под руководством Петра Сергеевича Новикова, который одним из первых в СССР начал заниматься проблемами вычислимости. Вместе с Алексеем Андреевичем Ляпуновым, также работавшим под руководством Новикова, Яблонский проводил в МГУ семинары по вопросам реализации булевых функций. Яблонский и Ляпунов организовывали и направляли всю исследовательскую деятельность в области теории вычислений.

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