Золотой билет

В 1956 году Курт Гёдель написал письмо Джону фон Нейману – пионеру в информатике и многих других областях науки. В письме Гёдель на немецком языке рассуждал о проблеме выполнимости и о вопросе равенства классов P и NP, только формулировал он этот вопрос в несколько иных терминах. По словам ученого, если бы мы жили в мире, в котором P = NP, то «математикам более не пришлось бы тратить время на задачи типа „да-нет“: этот труд за них выполняли бы машины <…> Впрочем, я уже перестал относить эту возможность к области несбыточного». Идеи Гёделя на пятнадцать лет опередили работы Левина и Кука.

Получил ли фон Нейман то письмо? Ответил ли он Гёделю? Мы этого не знаем; на тот момент фон Нейман уже был болен раком, и в 1957 году его не стало. О письме научное сообщество узнало лишь в конце восьмидесятых, когда за вопросом о равенстве P и NP уже прочно закрепился статус одной из центральных открытых научных проблем. Сам Гёдель умер в 1978 году; душевное расстройство, омрачившее последние годы его жизни, помешало ученому понять, что Кук в своей работе поднял тот же вопрос.

Так почему бы не назвать вопрос «проблемой Гёделя»? Почему не признать за Гёделем приоритет? Ведь он пришел к нему намного раньше, чем Кук и Левин! К сожалению, – или, возможно, к счастью, – в науке действует тот же принцип, что и в мореплавании: Христофор Колумб прославился не потому, что первым открыл Америку, а потому, что открыл ее последним. Впрочем, Гёдель тут и сам, как говорится, дал маху: не осознавая значимость поднятых в письме к фон Нейману вопросов, ученый никогда не публиковал свои идеи. Если смотреть на публикации, то первыми проблему равенства P и NP сформулировали все-таки Кук и Левин.

В 1993 году научное сообщество, отдавая дань Гёделю за его фундаментальный вклад в логику и высказанные в письме идеи, учредило премию в его честь. Премией Гёделя отмечают недавно появившиеся работы в области теоретической информатики.

Правило марсианина

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

Понятно, что цивилизации на Марсе нет и сравнивать нам там себя на самом деле не с кем, но мы ведь можем подключить воображение! Допустим, у марсиан имеется машина Экзигия – вычислительная модель, отличная от машины Тьюринга, но обладающая абсолютно теми же возможностями. Марсианский вариант тезиса Чёрча – Тьюринга гласит: все, что можно вычислить, вычислимо и на машине Экзигия. Значит, понятие вычислимости естественно, а вот понятие машины Тьюринга – нет.

В случае с классами P и NP можно обойтись без марсиан. Советские и американские математики практически не имели возможности общаться; они параллельно проделали одну и ту же работу и независимо сформулировали проблему равенства P и NP и понятие NP-полноты. Мотивы были разными: на Западе разбирались с вычислительной эффективностью, на Востоке – с необходимостью перебора; в результате обе стороны пришли туда же, куда и Курт Гёдель, опередивший их на пятнадцать лет.

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

Глава 6. Преодолевая трудности

Во второй главе мы с вами побывали в идеальном мире. Равенство P и NP сделало нашу жизнь прекрасной и удивительной. Исследовать можно было все. Оптимизировать – тоже. Машины умели выполнять почти все мыслимые и немыслимые операции. Прекрасно, волшебно, пугающе… и, скорее всего, нереально.

На самом деле мир наверняка далек от совершенства – этакая «неэлегантная вселенная», в которой P и NP не равны. Во всяком случае, именно в таком мире мы будем жить до тех пор, пока не найдем эффективный алгоритм для решения задач из NP. Но что же делать, если мы не можем эффективно решить какую-то задачу? Оставить на потом?

К сожалению, некоторые трудные задачи нельзя так просто взять и отмести. Гарри работает планировщиком на производственном предприятии «Рога и копыта». Его босс Эми поручает ему настроить линию на сборку последней модели мобильного телефона «Эйфон» и минимизировать при этом время сборки. Гарри читал предыдущие главы нашей книги, поэтому смело отвечает: «Извините, но эта задача NP-полная. Если даже известные ученые считают, что быстрого решения нет, то что уж мне пытаться? Я лучше в боулинг пойду поиграю». На что Эми разрешает ему веселиться хоть до утра, поскольку в «Рогах и копытах» он больше не работает.