Читать «Золотой билет. P, NP и границы возможного» онлайн - страница 67

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

Парадокс лжеца

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

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

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

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

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

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

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

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

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

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