Золотой билет

Во второй главе мы с вами побывали в идеальном мире. Равенство P и NP сделало нашу жизнь прекрасной и удивительной. Исследовать можно было все. Оптимизировать – тоже. Машины умели выполнять почти все мыслимые и немыслимые операции. Прекрасно, волшебно, пугающе… и, скорее всего, нереально.

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

К сожалению, некоторые трудные задачи нельзя так просто взять и отмести. Гарри работает планировщиком на производственном предприятии «Рога и копыта». Его босс Эми поручает ему настроить линию на сборку последней модели мобильного телефона «Эйфон» и минимизировать при этом время сборки. Гарри читал предыдущие главы нашей книги, поэтому смело отвечает: «Извините, но эта задача NP-полная. Если даже известные ученые считают, что быстрого решения нет, то что уж мне пытаться? Я лучше в боулинг пойду поиграю». На что Эми разрешает ему веселиться хоть до утра, поскольку в «Рогах и копытах» он больше не работает.

На место Гарри в срочном порядке наняли Джорджа. К счастью для себя, Джордж читал эту главу и потому сумел настроить линию на производство «Эйфонов». Неужели он изобрел гениальный алгоритм, который всегда оптимально распределяет подзадачи? Нет. Но с работой он все-таки справился? Безусловно.

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

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

Иногда NP-полная задача упорно не желает поддаваться. Что с ней делать? Перейти к другой NP-полной задаче. Или взять и плюнуть на все, потому что есть дела и поважнее.

Полный перебор

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

Однако раньше все было совсем по-другому. В 1971 году, когда Стивен Кук поднял вопрос о равенстве P и NP, компания Intel выпустила микропроцессор Intel 4004 – первый полноценный центральный процессор, который уместился на одном кристалле и стал доступным для потребителей. Intel 4004 мог выполнять 92000 операций в секунду и для того времени был очень скоростным.

Возьмем для примера подробно разобранную Куком задачу о выполнимости и рассмотрим случай с двадцатью переменными. Применим к ней простейший алгоритм, который методично перебирает все возможные комбинации значений переменных, устанавливая их в TRUE или FALSE. Если предположить, что на обработку одной комбинации уходит 100 шагов, то выполнимость всей формулы будет проверяться примерно 19 минут. Долго, конечно, но ведь могло быть и хуже! Однако проблема в том, что с двадцатью переменными каши особо не сваришь.

Двадцать пять переменных обрабатывались бы примерно 10 часов. Тридцать – чуть больше 13 суток. Ну а с сорока переменными мы бы ждали с 1971-го года по 2009-й.

Сейчас Intel каждый год выпускает несколько новых моделей процессоров. Рассмотрим, к примеру, появившийся в 2009-м Intel i7–870, который мог выполнять 2,93 миллиарда операций в секунду – в 30000 раз больше, чем Intel 4004. С сорока переменными он справился бы часов за десять, так что в 1971-м быстрее было бы просто подождать 38 лет и воспользоваться технологиями 2009-го.

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

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

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

Рис. 6.1. Коммивояжер: города с населением более 500 человек

Эвристические методы

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

Любой вычислительный алгоритм – это тоже метод решения какого-либо вопроса. Эвристические алгоритмы работают подобно правилу большого пальца: иногда они ошибаются, однако в большинстве случаев находят верное решение. Для NP-полных задач такие алгоритмы начали появляться задолго до того, как об их NP-полноте стало известно. За последние десятилетия сложными эвристическими методами «обзавелось» огромное множество трудоемких задач. Ни один из этих методов не является универсальным и не годится для всех случаев сразу, однако в общем и целом они со своей работой справляются.

Рис. 6.2. Карта Соединенных Штатов

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

Неваду окружает кольцо из пяти штатов: Калифорния, Орегон, Айдахо, Юта и Аризона. Для раскраски всех штатов кольца требуется не меньше трех цветов; Невада имеет с ними общие границы, так что для нее придется добавить четвертый. Другие штаты также образуют подобные кольца: к примеру, штат Кентукки окружают Теннесси, Вирджиния, Западная Вирджиния, Огайо, Индиана, Иллинойс и Миссури. Здесь нам тоже, как и в случае с Невадой, понадобится три цвета для кольца и четвертый для Кентукки.

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

На рисунке ниже представлена карта областей Армении.

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

Швейцарию окружает нечетное число соседей – пять. Это Франция, Италия, Австрия, Лихтенштейн и Германия. Несмотря на это, карту на рис. 6.5 тоже можно раскрасить в три цвета.

Дело в том, что Лихтенштейн вклинился между Швейцарией и Австрией и разбил их общую границу на две, поэтому Австрию нужно учитывать дважды. Оказывается, важно не количество соседних государств, а количество общих границ; у Швейцарии их шесть, а шесть – число четное. Заметим, что считаются только внешние границы, и страны, целиком лежащие внутри другого государства, не учитываются вообще (например, Ватикан внутри Италии).

Рис. 6.3. Армения

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

Эвристический метод имеет ровно два исключения.

1. На карте имеется озеро, по которому проходит граница между регионами. Например, озеро Мичиган отделяет Иллинойс от штата Мичиган.

Рис. 6.4. Раскраска Армении

2. Четыре или более регионов встречаются в одной точке. Например, Аризона, Нью-Мексико, Колорадо и Юта.

Впрочем, в случае с США исключения роли не играют, поскольку мы и так уже знаем, что цветов нужно четыре (не считая, разумеется, синего для озер).

В реальной жизни этот эвристический метод почти не ошибается. Ну а как он справится с картой воображаемого Королевства, на которой у любой провинции четное число соседей (четыре), и которую, однако, невозможно правильно раскрасить в три цвета (не считая, опять же, синего для озер)?

Рис. 6.5. Швейцария

Рис. 6.6. Раскраска Швейцарии

Каждая из одиннадцати провинций граничит ровно с четырьмя другими, при этом в ее «окружении» обязательно имеется озеро. Наш метод говорит, что карту Королевства можно правильно раскрасить в три цвета; однако он ошибается, поскольку при наличии лишь трех цветов какие-нибудь две провинции непременно окажутся одинаково окрашены.

Рис. 6.7. Карта Королевства заклятых друзей

Международная конференция The International Conference on Theory and Applications of Satisfiability Testing стремится охватить все аспекты проблемы выполнимости. Особое внимание уделяется хорошим эвристическим алгоритмам. В рамках конференции проводится конкурс SAT Race, в котором участвуют компьютерные программы по решению SAT-задач. Задачи для конкурса могут быть сгенерированы случайным образом, позаимствованы из различных областей науки и техники или же сконструированы специально с таким расчетом, чтобы решить их было крайне трудно. Многие программы-участники успешно справляются с задачами на миллион переменных.

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

Иголка в стоге сена

Предположим, мы ищем клику из трех человек среди всех 20000 жителей Королевства. По самым грубым подсчетам нужно проверить чуть больше триллиона вариантов – сущая ерунда для любого современного компьютера. Однако дальше варианты начинают размножаться с космической скоростью, перед которой компьютеры очень быстро пасуют: для клики размера четыре требуется уже 6 квадриллионов проверок, для клики размера пять – 26 квинтиллионов, а для клики размера шесть – 88 секстиллионов (т. е. 88 и 21 ноль).

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

Рис. 6.8. Дружеские связи

На представленной выше диаграмме Боб, Даниэль, Фрэнк и Гарри образуют очень приятную группу, поскольку все дружеские связи (линии на схеме) завязаны на них.

Рис. 6.9. Очень приятная группа размера четыре

А вот очень приятную группу размера три составить уже не получится. Например, если взять Элис, Чарли и Фрэнка – потеряются дружеские связи Ева – Даниэль и Джордж – Гарри.

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

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

При помощи подобных хитростей можно избежать полного перебора всех потенциальных вариантов при поиске небольших очень приятных групп. Для группы размера пять понадобится около 100000 проверок, для группы размера 10–200000 проверок, а для группы размера 30–601000 проверок; любой ноутбук справится с такой задачей за считаные доли секунды. Поиск очень приятной группы размера 113 потребует проверки триллиона вариантов и будет длиться не дольше, чем поиск клики из каких-то несчастных трех человек.

Рис. 6.10. Не очень приятная группа размера 3

Стоп. Выходит, очень приятные группы искать не так уж сложно? Но разве Карп не доказал, что поиск очень приятной группы минимального размера (т. е. минимального вершинного покрытия) – задача NP-полная? Дело в том, что у жителей Королевства друзей обычно очень много. Маловероятно, что все дружеские связи завязаны лишь на 113 жителях. А как только мы замахнемся на группы побольше, число вариантов тут же резко возрастет.

Например, для группы размера 150 потребуется уже 1,5 квадриллиона проверок, для группы размера 200 – более секстиллиона, а для группы размера 500 – примерно 38 сексдециллионов (т. е. 38 и 51 ноль). Поиск очень приятной группы минимального размера – задача практически неразрешимая. А вот если нам просто нужно убедиться, что в Королевстве не существует очень приятной группы размера сто, мы получим ответ за разумное время.

Приближенные методы

Оптимальное решение получается найти далеко не всегда. Очень часто, однако, не самое лучшее решение оказывается вполне удовлетворительным.

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

Предположим, вы хотите объехать 50 городов. Вам известно, что длина кратчайшего маршрута – 2800000 км. Если вы составите маршрут в 2810000 км, то вряд ли станете надрываться дальше из-за каких-то лишних 10000 км.

С другой стороны, если дорога обходится вам в доллар за километр, и за весь вояж вам заплатят 2805000 долларов, разница будет очень заметна: вы либо заработаете 5000 долларов (уложившись в 2800000 км), либо потеряете (удовлетворившись маршрутом в 2810000 км). Сократите длину пути до 2803000 км – и окажетесь в плюсе, хотя ваш маршрут не будет оптимальным.

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

На рисунке ниже вы видите карту Китая, на которой отмечено 71009 городов.

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

Рис. 6.11. Карта Китая

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

Если бы все NP-задачи решались приближенными методами настолько замечательно, поднимать вопрос о равенстве или неравенстве P и NP не имело бы особого смысла. Однако в действительности дела обстоят не так уж радужно. Рассмотрим, к примеру, задачу о клике – большой группе людей, в которой все между собой дружны. В общем случае алгоритмы поиска максимальной клики не дают нам хорошего приближения. За разумное время мы вряд ли доберемся даже до клики размера 15; а вдруг в Королевстве есть клика из 2000 жителей?

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

Рис. 6.12. Сетка на карте Китая

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

Мы с вами разобрали тривиальный случай, в котором можно методично перебрать все варианты и убедиться, что минимальная очень приятная группа состоит из четырех человек: Фрэнк, Даниэль, Гарри и Боб. Теперь предположим, что ответ нам неизвестен, и рассмотрим простой приближенный алгоритм поиска очень приятной группы минимального размера.

На первом шаге выберем любых двух друзей и отметим их; пусть это будут Элис и Гарри.

Теперь выберем еще двух друзей, ни один из которых пока не отмечен, и тоже их отметим.

Повторяем до тех пор, пока у нас имеются неотмеченные друзья.

В итоге все те, кого мы отметили, составят очень приятную группу.

Рис. 6.13. Дружеские связи – II

Рис. 6.14. Поиск очень приятной группы – II: шаг 1

Рис. 6.15. Поиск очень приятной группы – II: шаг 2

Рис. 6.16. Очень приятная группа размера шесть

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

Алгоритм подойдет для любой схемы дружеских связей. Если он, к примеру, отберет 50 дружеских пар и построит очень приятную группу из 100 человек, мы будем знать, что минимальный размер группы – от 50 до 100.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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