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

Рассмотренный выше простейший алгоритм последовательного отбора дружеских пар позволяет получить очень приятную группу, размер которой превышает минимальный не более чем в два раза (т. е. не более чем на 100 процентов). Если P ≠ NP, то мечтать о превышении меньше чем в 36 процентов смысла вообще не имеет. Но, может, удастся создать алгоритм, гарантирующий хотя бы 50-процентное превышение?

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

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

Другая задача

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

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

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

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

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

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

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

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

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