Глава 7. Как доказать, что P ≠ NP

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

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

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

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

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

«Невозможно разложить куб на два куба, биквадрат на два биквадрата и вообще никакую степень, большую квадрата, на две степени с тем же показателем. Я нашел этому поистине чудесное доказательство, но поля книги слишком узки для него».

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

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

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