Золотой билет. P, NP и границы возможного - Лэнс Фортноу

Потепление в отношениях между СССР и США началось в 1980-х. В седьмой главе мы поговорим о попытках разработать методы для доказательства неравенства P и NP, опирающиеся на теорию сложности схем; ведущую роль в этих разработках сыграл советский и российский математик Александр Разборов, бывший в ту пору студентом.

После распада Советского Союза пришел конец и вынужденной изоляции ученых. А с развитием интернета весь мир превратился в единое научно-исследовательское сообщество.

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

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

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

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

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

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

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

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

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

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

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

На место Гарри в срочном порядке наняли Джорджа. К счастью для себя, Джордж читал эту главу и потому сумел настроить линию на производство «Эйфонов». Неужели он изобрел гениальный алгоритм, который всегда оптимально распределяет подзадачи? Нет. Но с работой он все-таки справился? Безусловно.

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

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

Иногда NP-полная задача упорно не желает поддаваться. Что с ней делать? Перейти к другой NP-полной задаче. Или взять и плюнуть на все, потому что есть дела и поважнее.

Современные компьютеры считают очень быстро. Невероятно быстро. С невообразимой, умопомрачительной скоростью. Даже ноутбук или планшет может выполнить полный перебор потенциальных решений для задачи с небольшим размером входа.

Однако раньше все было совсем по-другому. В 1971 году, когда Стивен Кук поднял вопрос о равенстве P и NP, компания Intel выпустила микропроцессор Intel 4004 – первый полноценный центральный процессор, который уместился на одном кристалле и стал доступным для потребителей. Intel 4004 мог выполнять 92000 операций в секунду и для того времени был очень скоростным.