Изменчивая природа математического доказательства. Доказать нельзя поверить

Все эксперты сходятся на том, что задача разложения большого натурального числа на простые множители имеет экспоненциальную сложность[123] (т. е. для разложения n-значного числа требуется порядка 2ⁿ шагов). На этой гипотезе базируется знаменитый метод шифрования RSA — одна из передовых техник современной криптографии. Если мы научимся раскладывать на простые множители за полиномиальное время, то все RSA-закодированные сообщения можно будет быстро расшифровать[124]. В настоящее время неизвестно, относится ли задача разложения на простые множители к полиномиально сложным. Наилучшие известные алгоритмы требуют экспоненциального времени.

То же самое происходит с задачей о подграфе. О ней известно, что сложность ее экспоненциальна. Однако для заданных графа G, его подграфа K и еще одного графа H всего лишь полиномиально сложна задача проверить, изоморфен ли H подграфу K.

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

11.7.5 Недетерминистские машины Тьюринга

Недетерминистская машина Тьюринга (НДМТ) — это машина Тьюринга с дополнительной головкой, предназначенной только для записи и генерирующей наугад первоначальное значение, которое машина Тьюринга затем проверяет (точное определение понятия недетерминистской машины Тьюринга можно найти в [GAJ]). Мы говорим, что задача относится к классу NP, если существует многочлен p и недетерминистская машина Тьюринга, которая наугад генерирует значение длины n и останавливается, выдав ответ «да» или «нет» (т. е. определив, является угаданное значение верным или нет) не более чем за p(n) шагов.

Сразу же следует отметить, что (т. е. любая задача класса P относится также и к классу NP). Это утверждение очевидно: если П — задача класса P, то мы можем задать пустое решение, чтобы убедиться, что она принадлежит к классу NP тоже. Поэтому интересно рассмотреть множество NP\P (т. е. задачи класса NP, но не класса P).

Сразу же можно задать интересный вопрос: пусто множество NP\P или нет? Если нет, то любая задача из него обладает тем свойством, что детерминистски она сложна неполиномиально, но если ее решение попытаться угадать, то проверить догадку можно за полиномиальное время. Любая задача, про которую известно, что она попала в это множество, не допускает простого решения.

Оказывается, довольно сложно установить непустоту множества NP\P. До сих пор не обнаружено ни одной принадлежащей ему задачи; поэтому были сформулированы некоторые другие вопросы, на которые можно надеяться получить ответ. В частности, даже существуют сравнительно прямые методы доказательств, построенных для ответов на эти вопросы.

11.7.6 Основания NP-полноты

Первый из этих частных вопросов, основной вопрос NP-полноты, звучит так. Пусть имеется задача П. Можно ли установить истинность следующего силлогизма:

В работе [GAJ] рассмотрены некоторые задачи, которые допускают этот слегка модифицированный подход.

Самый интересный здесь вопрос — это вопрос NP\P-полноты. Мы обратимся к нему в разд. 11.7.8.

11.7.7 Полиномиальная эквивалентность

Мы говорим, что две задачи П₁ и П₂ полиномиально эквивалентны, если существует полиномиально сложный перевод с языка, на котором сформулирована П₁, на язык, на котором сформулирована П₂, и наоборот. Иначе говоря, существует многочлен q такой, что любое n символьное утверждение о П₁ может быть переведено в утверждение о П₁, в котором не более q(n) символов, и наоборот.

11.7.8 Определение NP-полноты

Пусть П₁ — задача из множества NP. Мы говорим, что задача П₁ NP-полна, если П₁ полиномиально эквивалентна любой другой задаче из множества NP. Если оказывается, что П₁ может быть решена с помощью алгоритма, требующего полиномиального времени, то любая другая задача из NP может быть решена за полиномиальное время. В то же время, если окажется, что любая задача из NP не допускает простого решения (т. е. принадлежит NP\P), то П₁ — тоже. NP-полные задачи считаются самыми сложными в NP.

11.8 Эндрю Уайлс и Великая теорема Ферма

Пьер де Ферма (1601–1665) — один из величайших математиков всех времен и народов. Всю свою сознательную жизнь он был магистратом или судьей города Тулузы во Франции. Его карьера отличалась осторожностью, честностью и безукоризненной справедливостью. Он вел тихую и продуктивную жизнь. Страстью его была математика. Возможно, он был самым талантливым математиком-любителем в истории. В рассказе о Ферма мы опираемся на работу [STA2], где подробно повествуется о его жизни.

В память о Ферма установлена большая статуя у здания городского совета в Тулузе. Ферма сидит, одетый в форменную судейскую мантию. На камне вырезана надпись (по-французски): «Ферма, отец дифференциального исчисления». На коленях у ферма сидит обнаженная муза, она скромно выказывает восхищение ментальной мощью Ферма.