Глава 5. Хроника предшествующих событий

В предыдущей главе мы рассказывали о не очень успешных попытках Дональда Кнута найти такой термин, который бы наилучшим образом отражал понятие NP-полноты. Если бы Кнут догадался повернуться на восток, в сторону СССР, то обнаружил бы там очень даже подходящее слово – «перебор». Метод перебора, или, как его еще называют, метод «грубой силы», заключается в последовательной проверке всех возможных вариантов в поисках наилучшего решения. Вопрос о равенстве классов P и NP можно переформулировать так: верно ли, что для задачи о клике работает лишь перебор, или можно найти и более быстрые методы?

Впрочем, в те времена американцам (в том числе Кнуту) сложно было разглядеть что-либо за железным занавесом, отделившим СССР и Восточную Европу от Европы Западной и от США после окончания Второй мировой. Холодная война породила острое соперничество между СССР и США; в пятидесятых обе страны начали активно развивать науку и технику в стремлении выиграть интеллектуальную гонку вооружений. К сожалению, железный занавес почти полностью изолировал друг от друга научные сообщества Востока и Запада. В семидесятых границы начали потихоньку открываться, однако полноценный диалог стал возможен лишь после окончания холодной войны, в 1991 году, когда соперничество наконец уступило место сотрудничеству. Сейчас научные работы выкладываются в интернет, а люди свободно путешествуют по миру. Научное сообщество ощущает себя единым целым; больше никаких противоборствующих лагерей!

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