Лэнс Фотноу - Золотой билет
Так благодаря особо трудной NP-задаче был спасен Цинциннати.
Весь боевой арсенал
Далеко не каждую трудную задачу из класса NP можно победить каким-то одним методом. Зачастую приходится применять сразу несколько способов из описанных выше. Когда стоящая перед нами задача никак не поддается, мы пытаемся изменить ее условия. Если новая задача снова оказывается NP-полной, мы атакуем ее эвристическими методами, которые хотя и не всегда дают точное решение, во многих случаях позволяют получить неплохое приближение.
Если P = NP, все эти ухищрения становятся не нужны, поскольку один-единственный алгоритм дает ключ ко всем проблемам сразу. Если же – как многим кажется – P и NP не совпадают, то в большинстве случаев мы все же можем что-то сделать. Возможно, нам потребуется довольно много времени; возможно, мы решим задачу, отличную от исходной; возможно, решение окажется далеким от оптимального… однако работа будет выполнена, а это уже неплохо.
Глава 7. Как доказать, что 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 года, заложившей основы теоретической информатики.
Любая компьютерная программа либо остановится и выдаст некий результат, либо будет работать бесконечно. Допустим, у нас есть алгоритм, который определяет, останавливается программа или нет. Применим его к самому себе и создадим программу, представленную на рисунке ниже.
Программа либо остановится, либо будет работать бесконечно. В любом случае мы придем к противоречию, а значит, наше допущение неверно, т. е. создать программу, которая бы для любой другой программы определяла, остановится она или нет, просто невозможно. Невозможно ни на стационарном компьютере, ни на ноутбуке. Невозможно ни сейчас, ни через сотню лет. Никто и никогда такую программу не напишет, потому что алгоритма, решающего проблему останова, просто-напросто не существует.
Рис. 7.4. Программа
А нельзя ли примерно таким же способом доказать, что некоторые задачи не могут быть решены эффективно, т. е. не принадлежат классу P, в котором для любой задачи существует эффективный алгоритм? Конечно же, можно!
Для начала определим алгоритм Q, который принимает на вход код программы R и решает следующую задачу:
• Если программа R, получив на вход свой собственный код, за полиномиальное время выдает ответ «Да», ответить «Нет».
• В противном случае ответить «Да».
Теперь возьмем произвольный эффективный алгоритм S. Очевидно, что Q(S) ответит «Да» в том и только в том случае, когда S(S) ответит «Нет», а это значит, что ни один эффективный алгоритм никогда не совпадет с алгоритмом Q.
Несмотря на это, алгоритм Q вполне корректный, и задача, которую он выполняет, разрешима, – вот только за полиномиальное время с ней не справиться.
Раз Q не принадлежит классу P, тогда, если бы мы доказали, что Q лежит в NP, т. е. любое заданное решение быстро проверяется, это означало бы, что P ≠ NP, и проблема тысячелетия была бы решена.
