Золотой билет - Страница 36

К оглавлению

36

А нестандартное поведение – это как раз то, что требуется Томасу: он не сможет подобрать секретный код, если карта работает как надо. Поврежденная (в меру) карта продолжает реагировать на запросы, вот только реакции ее уже могут быть не те, что прежде.

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

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

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

Время смириться

Если вам попался слишком крепкий орешек, все, что вы можете сделать, – это бросить его и заняться чем-то другим.

Ричард долго бился над химической формулой супернаркотика, который поможет ему захватить весь мир или – на худой конец – окрестности его родного Цинциннати. Под действием наркотика люди должны были становиться расслабленными и управляемыми. «Добавлю его в воду на очистительной станции Миллера, – мечтал он. – А когда все размякнут, приду и порабощу их!»

Для превращения мечты в реальность оставалось лишь обзавестись достаточным количеством необходимых ингредиентов. Проблема была в том, что после недавнего инцидента ему был вынесен судебный запрет на покупку химикатов. Не имея возможности официально обратиться в специализированную фирму, Ричард придумал использовать предметы домашнего обихода и экстрагировать из них требуемые вещества. Он составил внушительный перечень подходящих комбинаций товаров и ввел в компьютер множество параметров – цены, максимальное количество товара, которое, не навлекая подозрений, можно заказать за один раз, адреса двадцати «Волмартов» и четырнадцати «Таргетов» в Цинциннати и окрестностях, а также стоимость доставки и аренды складов (ясно было, что склад понадобится, причем точно не один). Вдобавок от компьютера требовалось минимизировать время и расходы. К огромному огорчению Ричарда, потенциальных вариантов оказалось слишком много, и проверить их все было совершенно нереально. Ричард чувствовал, что решение где-то рядом; он перепробовал все найденные в интернете алгоритмы, однако ни приближенные методы, ни эвристические не приблизили его к заветной цели ни на шаг. В конце концов он все же сдался и вернулся к основной работе – охранником на фабрике по производству зубной пасты.

Так благодаря особо трудной NP-задаче был спасен Цинциннати.

Весь боевой арсенал

Далеко не каждую трудную задачу из класса NP можно победить каким-то одним методом. Зачастую приходится применять сразу несколько способов из описанных выше. Когда стоящая перед нами задача никак не поддается, мы пытаемся изменить ее условия. Если новая задача снова оказывается NP-полной, мы атакуем ее эвристическими методами, которые хотя и не всегда дают точное решение, во многих случаях позволяют получить неплохое приближение.

Если P = NP, все эти ухищрения становятся не нужны, поскольку один-единственный алгоритм дает ключ ко всем проблемам сразу. Если же – как многим кажется – P и NP не совпадают, то в большинстве случаев мы все же можем что-то сделать. Возможно, нам потребуется довольно много времени; возможно, мы решим задачу, отличную от исходной; возможно, решение окажется далеким от оптимального… однако работа будет выполнена, а это уже неплохо.

Глава 7. Как доказать, что P ≠ NP

Юрис Хартманис, один из основоположников теории вычислительной сложности, любит повторять: «Все знают, что они не равны, а доказать не могут».

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

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

Последующие десятилетия ознаменовались невероятными успехами в математике и кибернетике; удалось разрешить даже одну из самых знаменитых математических проблем – Великую теорему Ферма.

В 1637 году француз Пьер де Ферма, математик-любитель и юрист по профессии, сделал на полях своей древнегреческой «Арифметики» следующее замечание:

...

«Невозможно разложить куб на два куба, биквадрат на два биквадрата и вообще никакую степень, большую квадрата, на две степени с тем же показателем. Я нашел этому поистине чудесное доказательство, но поля книги слишком узки для него».

36