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

Том отправился в ресторан, чтобы сообщить плохие новости. Это был его первый провал: до сих пор ему всегда удавалось помочь Джейн с рецептом. «Мы можем хоть немного изменить условия задачи? Требования ко вкусу, например? – поинтересовался он. – Иначе никакого соуса не будет». В ответ Джейн заявила, что ничего менять нельзя и что вкус и консистенция должны быть в точности такими, как она просила, – в противном случае блюдо будет безнадежно испорчено. «А как насчет самой запеканки?» – осенило Тома.

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

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

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

Допустим, некий Томас из обслуживающего персонала отеля позаимствовал смарт-карту Энни, пока та плавала в бассейне. У Томаса есть специальный кардридер, который посылает карте определенные данные и анализирует ее ответ. Если P окажется равно NP, то такой кардридер будет быстро подбирать секретный ключ, и смарт-карты станут совершенно бесполезны. Но пока мы с вами живем в мире, где P и NP не равны, так что поиск ключа представляет собой задачу огромной вычислительной трудности. Протоколы для смарт-карт специально разрабатывают таким образом, чтобы у методов, описанных в этой главе, не осталось ни единого шанса, будь то грубый поиск или хитрый эвристический алгоритм. Обычный мошенник, потерпев неудачу, просто возвратил бы Энни ее карту, а если бы Энни обнаружила пропажу раньше, то позвонила бы в банк и попросила эту карту заблокировать.

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

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

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

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

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

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

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

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

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

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

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