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

Текущее положение дел

Мы еще никогда не были настолько далеки от решения проблемы P и NP. Не в том смысле, что для этого требуется огромная подготовительная работа; просто мы уже испробовали все мыслимые и немыслимые подходы и исчерпали все известные науке методы доказательства, так что в ближайшем будущем прогресса ждать не приходится.

Единственную на сегодняшний момент потенциальную возможность открыл Кетан Мулмулэй из Чикагского университета. Ученый показал, что решение некоторых трудных проблем из области математики под названием «алгебраическая геометрия» (и это не помесь школьной алгебры и геометрии, а нечто гораздо более сложное) может дать ключ к доказательству неравенства P и NP. Вот только для решения этих алгебраически-геометрических проблем потребуются такие техники, которых в нашем арсенале нет и которые в ближайшее время вряд ли появятся. Несколько лет назад Мулмулэй предположил, что реализация этого плана займет около ста лет. Теперь тот прогноз уже кажется ему чересчур оптимистичным.

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

Глава 8. Совершенно секретно

У каждого из нас есть секреты. Как минимум мы храним в тайне пароли и не желаем, чтобы кто-то читал нашу почту. Если P ≠ NP, то секреты есть и у NP-полных задач: это их решения, найти которые не так-то просто. В 1976 году Уитфилд Диффи и Мартин Хеллман предложили шифровать информацию при помощи класса NP. В истории криптографии, т. е. науки о шифровании, наступил поворотный момент.

Очень краткая история классической криптографии

Шифрование существует столько же, сколько и переписка. Юлий Цезарь пользовался простым подстановочным шифром, в котором каждая буква заменялась на другую букву, отстоящую от нее в алфавите на три позиции.

Фраза The early bird gets the worm («Кто рано встает, тому бог дает») после такой кодировки превращается в Wkh hduob elug jhwv wkh zrup. Способ шифрования, при котором все буквы циклически сдвигаются на определенное число позиций, стали называть шифром Цезаря.

В Древнем Риме этот метод работал хорошо. Зашифрованные сообщения выглядели как случайный набор букв, а люди пока еще не обладали необходимыми навыками для взлома шифров. К IX веку математики разработали методы восстановления исходного сообщения; эти методы учитывали частоту появления букв и анализировали короткие слова. Глядя на фразу Wkh hduob elug jhwv wkh zrup, можно заметить, что буква h встречается четыре раза, т. е. чаще остальных. Самая распространенная буква английского алфавита – это e, ее частота составляет примерно 12 процентов. Вы можете предположить, что буква h кодирует букву e, – и будете совершенно правы. Сочетание wkh встречается дважды; вы уже знаете, что h – это e, поэтому делаете вывод, что wkh – это, наверно, the. Еще чуть-чуть – и исходное сообщение будет восстановлено!