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

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

Если P равно NP, то мы сможем отыскать минимальную очень приятную группу быстро и эффективно. А если не равно? Тогда в общем случае мы будем получать лишь группы, размер которых превышает минимальный более чем на 36 процентов. Любой алгоритм, гарантирующий превышение ровно в 36 процентов или менее, можно преобразовать таким образом, чтобы он решал произвольную NP-полную задачу. Возможность этого преобразования основывается на целом ряде важных и серьезных результатов, полученных в период между 1990 и 2005 годами.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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