Золотой билет. P, NP и границы возможного - Лэнс Фортноу

Юрис Хартманис, один из основоположников теории вычислительной сложности, любит повторять: «Все знают, что они не равны, а доказать не могут».

В предыдущих главах мы познакомились с проблемой равенства P и NP, узнали, в чем ее суть и почему она так важна, совершили путешествие в идеальный мир, в котором P = NP и который вряд ли когда-нибудь станет реальностью, а также научились обращаться с трудными задачами в мире, где P и NP не равны.

Для математиков вопрос о равенстве классов превратился в настоящий вызов. С тех пор как Кук, Карп и Левин сформулировали проблему и показали ее важность, ученые во всем мире пытаются найти строгое математическое доказательство равенства – или неравенства – P и NP. Классические методы давно потерпели поражение; еще к концу семидесятых в математическом сообществе сложилось мнение, что для решения данной проблемы, по всей видимости, требуется особый, принципиально новый подход.

Последующие десятилетия ознаменовались невероятными успехами в математике и кибернетике; удалось разрешить даже одну из самых знаменитых математических проблем – Великую теорему Ферма.

В 1637 году француз Пьер де Ферма, математик-любитель и юрист по профессии, сделал на полях своей древнегреческой «Арифметики» следующее замечание:

Рис. 7.1. Комикс про Дилберта. © Скотт Адамс, 1997. Публикуется с разрешения UNIVERSAL UCLICK. Все права защищены

Другими словами, не существует таких натуральных чисел a, b, c и такого натурального n > 2, что an + bn = cn. Ученый больше нигде не упоминает об этом доказательстве; вполне возможно, что строгое математическое обоснование он так и не придумал. Постепенно теорема приобрела широкую известность и пополнила ряды классических «нерешаемых» математических задач. Знаменитую теорему мечтали доказать даже дети. Один из таких мечтателей (среди которых был и я), став взрослым, превратил мечту в реальность. В 1994 году Эндрю Уайлс из Принстонского университета представил доказательство, основанное на целом ряде работ по теории чисел, и в один миг стал знаменитым – насколько вообще бывают знаменитыми математики.

Здесь вы не найдете ключ к решению вопроса «P против NP», иначе это была бы совсем другая книга. Цель данной главы – познакомить вас с некоторыми идеями и методами, разработанными в попытке доказать неравенство P и NP. К сожалению, ни одна из этих идей не приблизила математиков к решению проблемы. По сути, для доказательства неравенства необходимо показать, что некоторые задачи из класса NP не могут быть эффективно решены ни одним из известных – а также неизвестных – алгоритмов. Вообще доказать неосуществимость чего-либо крайне трудно, однако нельзя утверждать, что это невозможно логически. Шансы у нас есть; будем надеяться, что когда-нибудь эту проблему – вероятно, наиболее трудную и важную среди всех математических проблем, – все-таки решат.

Давайте рассмотрим одно загадочное утверждение.

Рис. 7.2. Утверждение

Оно истинно или ложно, как вам кажется? Если оно ложно, значит, неверно то, что оно ложно, а значит, оно истинно. Но если оно истинно – значит, верно то, что оно ложно. С какой стороны ни зайди, получишь противоречие. Этот парадокс получил название «парадокс лжеца». Сейчас я лгу. Ну как – солгал я или нет?

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

В 1930 году Курт Гёдель пришел к выводу, что о математических доказательствах можно рассуждать на языке самой математики и что высказывания о возможности доказательства того или иного утверждения также могут быть записаны в виде формальных математических утверждений. Ученый изобрел высказывание, которое говорит о возможности собственного доказательства, и сформулировал его на языке математики. Вот оно:

Рис. 7.3. Утверждение о возможности доказательства

Похоже на предыдущее, правда? Предположим, что оно ложно. Тогда его можно доказать, а следовательно, оно истинно. Но это противоречит первоначальному предположению о том, что оно ложно; значит, оно истинно.

Что, опять парадокс? Вообще-то нет: высказывание истинно, вот только это не докажешь. Так Гёдель одним махом пошатнул все фундаментальные основы математики: оказывается, некоторые истинные утверждения невозможно доказать[5]!

Допустим, знакомый говорит вам, что у него есть волшебная шкатулка, которая предсказывает будущее. Попросите его поинтересоваться у этой шкатулки, какой рукой вы его ударите – правой или левой? Если шкатулка ответит «левой», ударьте правой, а если «правой» – ударьте левой. Шкатулка ошибется в любом случае.

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

Начнем с простого наблюдения: программа – это набор данных. Такой же, как, к примеру, файл Word или Excel. Поэтому одна программа вполне может проанализировать код другой программы. Впервые подобная мысль была высказана Аланом Тьюрингом в его знаменитой работе 1936 года, заложившей основы теоретической информатики.

Любая компьютерная программа либо остановится и выдаст некий результат, либо будет работать бесконечно. Допустим, у нас есть алгоритм, который определяет, останавливается программа или нет. Применим его к самому себе и создадим программу, представленную на рисунке ниже.