Золотой билет. P, 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, чтобы увеличить вычислительную мощность, и какое-то время витал в облаках. Ничто не помогало; отчаявшись найти решение самостоятельно, он обратился к друзьям из Силиконовой долины. Тому, кто первым подберет ингредиенты для соуса, Том обещал драгоценную бронь в ресторане «У Тьюринга». Однако через неделю сдались и «силиконщики»: было ясно, что задача им не по зубам.