Лэнс Фотноу - Золотой билет

Рис. 4.12.Выпуклый многогранник

Алгоритмов стало два, причем друг на друга они абсолютно не походили; один прекрасно работал на практике, другой – в теории.

В 1984 году индийский математик Нарендра Кармаркар разработал метод внутренней точки, который тоже, как и симплекс-метод, выполняет обход многогранника, вот только «ходит» он не по внешним точкам, а по внутренним. В теории метод внутренней точки сравним по быстроте с методом эллипсоидов, а на практике он после некоторых доработок может поспорить с симплекс-методом.

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

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

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

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

Поиск эффективных алгоритмов начался около 3000 лет назад, когда люди впервые стали применять арифметику для ускорения процесса сложения больших чисел. Однако наша отправная точка – тридцатые годы прошлого века: именно в этот период зародилась теория алгоритмов.

Мы освоили космос. Телескопы переносят нас в отдаленные уголки галактики, позволяя изучать историю развития Вселенной. Через микроскопы мы наблюдаем за атомами; мы даже изобрели огромные машины, в которых эти атомы сталкиваются, распадаясь на еще более мелкие частички. А еще мы расшифровали человеческий геном. И все же одну из самых главных загадок представляет собой то небольшое устройство, которым мы ежедневно пользуемся дома, в машине, и даже носим в кармане. Мы называем его компьютером. Так что же это такое?

Слово computer появилось еще в XVII веке. В те времена никому и в голову не приходило изобретать машины, которые бы что-либо вычисляли. Компьютерами, или вычислителями, называли мастеров счета, занимавшихся вычислениями профессионально. С развитием банковской системы на вычислителей «свалились» еще и вклады и кредиты.

Согласно Оксфордскому словарю, для обозначения механического счетного устройства слово computer впервые применили в 1897 году, а для электронного – в сороковых годах прошлого века. Так от людей-вычислителей термин перешел к огромным установкам из нескольких вычислительных машин, а затем и к компьютерам, которыми мы пользуемся сейчас.

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

А как обстоит дело с самим процессом вычисления? Есть ли что-то такое, что вычислению не поддается? Вопрос был решен еще до появления вычислительных машин: в 1936 году ответ на него дал великий математик Алан Тьюринг. Размышляя над тем, как рассуждают математики, Тьюринг пришел к формальной математической модели вычислительного процесса, которая впоследствии стала классической. Теперь ее называют машиной Тьюринга.

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

Машина Тьюринга казалась очень простой, однако, по словам ученого, на ней можно было вычислить все, что вообще поддавалось вычислению. Почти в то же самое время Алонзо Чёрч сделал аналогичное заявление относительно своего лямбда-исчисления, которое считают предшественником языков программирования. Тезис Чёрча – Тьюринга выдержал испытание временем, хотя сформулирован он был еще до изобретения современных компьютеров. Все, что поддается вычислению, вычислимо и на машине Тьюринга; по своим вычислительным возможностям она не уступит любому современному компьютеру, так что о ее чересчур примитивном устройстве можно не беспокоиться.