Упражнения с решениями - Урок 8 - NP-полнота и вычислительная неразрешимость

Упражнение с решением 1

Вы консультируете небольшую компанию, которая управляет компьютерной системой с повышенным уровнем безопасности для выполняемой засекреченной работы. Чтобы система не использовалась в незаконных целях, на ней работает служебная программа для сохранения IP-адресов, по которым обращаются пользователи. Предполагается, что каждый пользователь в любую минуту обращается не более чем по одному IP-адресу; программа записывает в файл для каждого пользователя u и каждой минуты m значение I(u, m), равное IP-адресу, к которому пользователь и обращался в минуту m. Если пользователь u в минуту m не обращался ни по какому IP-адресу, то I(u, m) присваивается нуль-символ ⊥.

Руководство компании только что узнало, что вчера система была использована для проведения сложной атаки на удаленные сайты. Атака проводилась с обращением к t разным IP-адресам за tпоследовательных минут; в минуту 1 атакующий обращался по адресу i₁, в минуту 2 он обращался по адресу i₂; и т. д. вплоть до адреса i_t в минуту t.

Кто же несет ответственность за атаку? Руководство компании проверяет файлы журналов и, к своему удивлению, выясняет, что нет ни одного пользователя и, который бы обращался по всем атакованным IP-адресам в соответствующее время; другими словами, нет такого и, что I(u, m) = i_m для каждой минуты m от 1 до t.

Неужели атака была совместно проведена небольшой группой из k пользователей? Подмножество S пользователей будет называться подозрительной группой, если в каждую минуту m от 1 до tбыл по крайней мере один пользователь u ∈ S, для которого I(u, m) = i_m. (Другими словами, к каждому IP-адресу в соответствующий момент обращался по крайней мере один пользователь из группы.)

Итак, для заданного набора всех значений I(u, m) и числа k существует ли подозрительная группа с размером не более k?

Решение

Прежде всего, задача о подозрительной группе очевидно принадлежит NP: если нам предъявят множество S пользователей, то мы можем проверить, что размер S не превышает k и в каждую минуту m от 1 до t по крайней мере один из пользователей S обращался к IP-адресу i_m.

Мы хотим найти заведомо NP-полную задачу и свести ее к задаче о подозрительной группе. Хотя эта задача имеет несколько характеристик (пользователи, минуты, IP-адреса), совершенно очевидно, что она является задачей покрытия (в соответствии с классификацией, описанной в этой главе): требуется найти объяснение для всех t подозрительных обращений, с ограничением количества пользователей (к). Когда мы решаем, что это задача покрытия, будет естественно попытаться свести к ней задачу о вершинном покрытии или покрытии множества. А для этого полезно вытеснить большинство усложняющих аспектов, оставив минимум, необходимый для кодирования задачи о вершинном покрытии или покрытии множества.

Сосредоточимся на сведении задачи о вершинном покрытии. В этой задаче необходимо найти покрытие для каждого ребра, при этом разрешено использовать всего k узлов. В задаче о подозрительной группе требуется “покрыть” все обращения и при этом разрешено использовать только k пользователей. Этот параллелизм дает веские основания полагать, что для заданного экземпляра задачи о вершинном покрытии, состоящего из графа G = (V, E) и границы к, следует построить экземпляр задачи о подозрительной группе, в которой пользователи соответствуют узлам G, а подозрительные обращения — ребрам.

Итак, предположим, что граф G в экземпляре задачи о вершинном покрытии состоит из m ребер e₁, ..., e_m, и e_j = (v, w). Экземпляр задачи о подозрительной группе строится следующим образом: для каждого узла G создается пользователь, а для каждого ребра e_t = (v_t, w_t) создается минута t. (Так что всего будет m минут.) В минуту t пользователи, связанные с двумя концами e_t, обращаются к IP-адресу i_t, а все остальные пользователи не обращаются ни к чему. Наконец, атака состоит из обращений по адресам i₁, i₂, ..., i_m в минуты 1, 2, ..., m соответственно.

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

(8.28) В построенном экземпляре задачи подозрительная группа с размером не более к существует в том, и только в том случае, если граф G содержит вершинное покрытие с размером не более k.

Доказательство. Сначала предположим, что G содержит вершинное покрытие C с размером не более k. Теперь рассмотрим соответствующее множество S пользователей в экземпляре задачи о подозрительной группе. Для всех t от 1 до m по крайней мере один элемент C является концом ребра е_t, и соответствующий пользователь в S обращался к IP-адресу i_t. Следовательно, множество S является подозрительной группой.

И наоборот, предположим, что существует подозрительная группа S с размером не более k, и рассмотрим соответствующее множество узлов C в G. Для всех t от 1 до m по крайней мере один пользователь из S обращался к IP-адресу i_t, и соответствующий узел в C является концом ребра е_t. Отсюда следует, что множество S является вершинным покрытием. ■

Упражнение с решением 2

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

Всего имеется п возможных лекторов, и в неделю с номером i (для i = 1, 2, ..., l) доступно подмножество L_i лекторов для проведения лекций.

С другой стороны, каждый проект требует наличия определенной подготовки, чтобы студенты могли успешно завершить его. В частности, для каждого проекта j (для j = 1, 2, ..., p) определено подмножество Р_j лекторов; чтобы завершить проект, студент должен посетить лекцию хотя бы одного из лекторов подмножества Р_j.

Итак, задача: для заданных множеств можно ли выбрать ровно одного лектора для каждой из первых l недель семинара, чтобы выбирались только лекторы, свободные в соответствующую неделю, а для каждого проекта j студенты прослушали как минимум одного из лекторов соответствующего множества Р_j? Назовем ее задачей планирования лекций.

Чтобы прояснить ситуацию, рассмотрим следующий пример. Допустим, l = 2, p = 3 и доступны n = 4 лектора, обозначенные A, B, C, D. Доступность лекторов определяется множествами L₁ = {A, B, C} и L₂ = {A, D}. Необходимые докладчики для каждого проекта определяются множествами Р₁ = {B, C}, Р₂ = {A, B, D} и Р₃ = {C, D}. В этом случае ответ для экземпляра задачи будет положительным: в первую неделю выбирается лектор B, а во вторую лектор D; для каждого из трех проектов студенты посетят лекцию хотя бы одного из необходимых лекторов.

Докажите, что задача планирования лекций является NР-полной.

Доказательство. Задача принадлежит NP, так как для заданной последовательности лекторов мы можем проверить, что (a) все лекторы свободны в назначенные им недели и (b) что для каждого проекта был выбран хотя бы один из необходимых лекторов.

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

Однако существует менее очевидное представление задачи планирования лекций, типичное для широкого диапазона задач на соблюдение ограничений. Это представление было весьма живописно отражено в “Нью-Йоркере” при описании стиля перекрестного допроса адвоката Дэвида Бойеса: во время перекрестного допроса Дэвид словно неспешно прогуливается со свидетелем по коридору, одновременно незаметно закрывая двери. Дойдя до конца коридора, Дэвид поворачивается к свидетелю — и выясняется, что отступать уже некуда. Все двери закрыты³.

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

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

Задача 3-SAT — канонический пример задачи с двухфазной структурой, описанной выше: сначала мы перебираем переменные, присваивая каждой true или false; затем перебираем все условия и смотрим, выполняются ли они с выбранными значениями. Эта параллель с задачей планирования лекций уже предполагает естественное сведение, демонстрирующее, что 3-SAT ≤_рПланирование лекций: мы определяем задачу так, чтобы выбор лекторов задавал переменные, после чего возможность реализации проектов представляет выполнение условий.

Допустим, имеется экземпляр задачи 3-SAT, состоящий из условий С₁, ..., С_k по переменным x₁, x₂, ..., x_n. Построим экземпляр задачи планирования лекций следующим образом: для каждой переменной х. создаются два лектора z_i и z'_i, соответствующие переменной х и ее отрицанию. Сначала идут n недель лекций; в неделю i доступны только лекторы z_i и z'_i. Далее следует серия из k проектов; для проекта j множество необходимых лекторов P_j состоит из трех лекторов, соответствующих литералам в условии С_j. Теперь, если для экземпляра 3-SAT существует выполняющее присваивание v, то в неделю i мы выбираем лектора между z_i и z'_i, соответствующего значению, присвоенному х_i в результате v; в этом случае будет выбран как минимум один лектор из каждого необходимого множества P_j. И наоборот, если можно найти вариант выбора лекторов, включающий как минимум одного лектора из каждого необходимого множества, мы сможем задать переменные х_i следующим образом: х_i присваивается 1, если выбран z_i, или присваивается 0, если выбран z'_i. В этом случае по крайней мере одна из трех переменных в каждом условии C_j получит значение, с которым это условие выполнено, поэтому данное присваивание является выполняющим. На этом завершается как сведение, так и доказательство его правильности.

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

Для заданных входных данных для задачи о вершинном покрытии, состоящих из графа G = (F, Е) и числа k, создается лектор z_v для каждого узла v. Мы присваиваем l = k и определяем L₁ = L₂= ... = L_k = {z_v: v ∈ V}. Другими словами, для первых k недель доступны все лекторы. После этого мы создаем проект j для каждого ребра e_j = (v, w), с множеством P_j = {z_v, z_w}.

Далее, если существует вершинное покрытие S, состоящее не более чем из k узлов, рассмотрим множество лекторов Z_S = {z_v: v ∈ S}. Для каждого проекта P_j по крайней мере один из необходимых лекторов принадлежит Z_S, так как S покрывает все ребра в G. Кроме того, мы можем планировать всех лекторов в Z_S на протяжении первых k недель. Из этого следует, что мы имеем действительное решение экземпляра задачи о планировании лекций.

И наоборот, предположим, что существует действительное решение экземпляра задачи о планировании лекций; пусть T — множество всех лекторов, выступающих в первые k недель. Обозначим X множество узлов G, соответствующих лекторам в T. Для каждого проекта P_j по крайней мере один из двух необходимых лекторов присутствует в T, а следовательно, по крайней мере один конец каждого ребра е_j входит в множество X. Таким образом, X — вершинное покрытие, содержащее не более k узлов.

Это завершает доказательство того, что Вершинное покрытие ≤_р Планирование лекций.

Упражнения

1. Для каждого из следующих двух вопросов выберите вариант ответа: (i) “Да”, (ii) “Нет” или (iii) “Неизвестно, потому что это привело бы к ответу на вопрос о P = NP”. Приведите краткое объяснение своего ответа.

(а) Определим версию задачи интервального планирования из главы 4 следующим образом: для заданного набора интервалов и границы k существует ли подмножество неперекрывающихся интервалов с размером не менее k?

Вопрос: Можно ли утверждать, что Интервальное планирование ≤_р Вершинное покрытие?

(b) Вопрос: Можно ли утверждать, что Независимое множество ≤_р Интервальное планирование?

2. Для анализа поведения покупателей в магазинах часто ведется двумерный массив A, строки которого соответствуют клиентам, а столбцы — продаваемым товарам. Элемент A[i, j] определяет количество единиц товараj, приобретенных покупателем i. Ниже приведен небольшой пример такого массива.

	Моющее средство	Пиво	Пеленки	Наполнитель для кошачьего туалета
Радж	0	6	0	3
Аланис	2	3	0	0
Челси	0	0	0	7

Один из способов обработки полученных данных выглядит так: допустим, подмножество S покупателей называется разнородным, если никакие два покупателя из S никогда не покупали один и тот же товар (то есть каждый товар был куплен не более чем одним покупателем из S). Например, разнородное множество покупателей может пригодиться для проведения маркетингового исследования.

Теперь мы можем определить задачу о разнородном множестве следующим образом: для заданного массива A размером m х n, определенного выше, и числа k ≤ m существует ли разнородное подмножество, содержащее не менее k покупателей?

Покажите, что задача о разнородном множестве является NР-полной.

3. При организации летнего спортивного лагеря возникает следующая задача. В лагере должен быть как минимум один квалифицированный тренер для каждого из n видов спорта (баскетбол, волейбол и т. д.). Организаторы получают заявки от m потенциальных тренеров. Для каждого из n видов спорта существует подмножество из m претендентов, квалифицированных в этом в виде спорта. Вопрос заключается в следующем: для заданного числа k < m возможно ли нанять не более k тренеров, чтобы для каждого из n видов спорта нашелся хотя бы один квалифицированный тренер? Назовем эту задачу задачей эффективного найма.

Покажите, что задача эффективного найма является NР-полной.

4. Предположим, вы занимаетесь администрированием высокопроизводительной системы реального времени, в которой асинхронные процессы работают с общими ресурсами. В системе существует множество из n процессов и множество из m ресурсов. В любой заданный момент времени каждый процесс определяет набор ресурсов, которые он намеревается использовать. Каждый ресурс может запрашиваться сразу несколькими процессами, но использоваться в любой момент времени он может только одним процессом. Ваша задача — распределить ресурсы между запрашивающими их процессами. Если процесс получает все запрошенные им ресурсы, он остается активным; в противном случае его выполнение блокируется. Соответственно задача резервирования ресурсов формулируется следующим образом: для заданных множество процессов и ресурсов, множества запрашиваемых ресурсов для каждого процесса и числа k возможно ли распределить ресурсы между процессами так, чтобы не менее k процессов оставались активными?

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

(a) Общая задача резервирования ресурсов, определенная выше.

(b) Частный случай задачи при k = 2.

(c) Частный случай задачи с двумя типами ресурсов (допустим, люди и оборудование); каждый процесс запрашивает максимум один ресурс каждого типа (другими словами, каждый процесс запрашивает одного конкретного человека и одно конкретное устройство).

(d) Частный случай задачи, в котором каждый ресурс запрашивается максимум двумя процессами.

5. Рассмотрим множество A = {a₁, ..., a_n} и набор B₁, B₂, ..., B_m подмножеств A (то есть B_i ⊆ A для всех i).

Множество H ⊆ A называется множеством представителей для набора B₁, B₂, ..., B_m, если H содержит минимум один элемент из каждого B_i — то есть если H ∩ B_i не пусто для каждого i (таким образом, H содержит “представителей” из всех множеств B_i).

Задача множества представителей определяется следующим образом: имеется множество A = {a₁, ..., a_n}, набор B₁, B₂, ..., B_m подмножеств A и число k. Существует ли множество представителей H ⊆ A для B₁, B₂, ..., B_m, размер которого не превышает k?

Докажите, что задача множества представителей является NР-полной.

6. Рассмотрим экземпляр задачи выполнимости, заданный условиями С₁, ..., С_k по множеству булевых переменных x₁, ..., x_n. Экземпляр называется монотонным, если литерал в каждом условии состоит из неинвертированной переменной, то есть каждый литерал равен х_i для некоторого i, а не Монотонные экземпляры задачи выполнимости решаются очень легко: они всегда выполнимы присваиванием каждой переменной 1.

Предположим, имеются три условия

Экземпляр является монотонным, и присваивание, задающее все три переменные равными 1, действительно выполняет все условия. Но это не единственное выполняющее присваивание; также можно было присвоить x₁ и x₂ значение 1, а x₃ значение 0. В самом деле, для любого монотонного экземпляра естественно задать вопрос о минимальном количестве переменных, которым необходимо присвоить 1 для его выполнения.

Задача монотонной выполнимости с минимумом истинных переменных формулируется так: для заданного монотонного экземпляра задачи выполнимости и числа k существует ли выполняющее присваивание для экземпляра, в котором не более k переменных задано значение 1? Докажите, что задача является NР-полной.

7. Так как задача о трехмерном сочетании является NР-полной, естественно ожидать, что аналогичная задача о четырехмерном сочетании будет хотя бы не менее сложной. Определим четырехмерное сочетание следующим образом: для заданных множеств W, X, Y и Z, каждое из которых имеет размер n, и набора C упорядоченных четверок в форме (w_i, x_j, у_k, z_l) существуют ли n четверок из C, среди которых никакие два не имеют общих элементов?

Докажите, что задача о четырехмерном сочетании является NР-полной.

8. Малолетняя дочь ваших знакомых Мэдисон учится читать. Чтобы помочь ей, родители купили набор цветных магнитов на холодильник с буквами алфавита (несколько экземпляров буквы A, несколько экземпляров буквы B и т. д.). При последней встрече вы строили из магнитов слова, которые она уже знает. Изначальные условия игры немного изменились. Вскоре вы пытались строить слова так, чтобы использовать все магниты из набора — то есть выбирали слова, которые она уже знает, но так, чтобы после выкладывания всех слов каждый магнит участвовал в записи ровно одного слова. (Разрешается повторение слов; например, если в набор магнитов входят по два экземпляра букв C, A и T, слово CAT можно построить дважды.)

Задача оказалась довольно сложной, и только позднее вы поняли причину. Допустим, мы рассматриваем обобщенную версию задачи использования всех магнитов, в которой английский алфавит заменяется произвольным набором символов, а словарь Мэдисон моделируется произвольным набором строк из символов этого набора. Цель остается той же, что в предыдущем абзаце. Докажите, что задача использования всех магнитов является NР-полной.

9. Вы управляете сетью передачи данных, моделируемой направленным графом G = (V, E). Имеется с пользователей, которые намерены использовать эту сеть. Пользователь i (для всех i = 1, 2, ..., c) выдает запрос на резервирование пути Р_i в графе G, по которому должны передаваться данные.

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

Итак, задача о выборе путей формулируется следующим образом: для направленного графа G = (V, E), множества запросов Р₁, Р₂, ..., Р_с (каждый из которых определяет путь в G) и числа к возможно ли выбрать как минимум к путей, чтобы никакие два из выбранных путей не содержали общих узлов?

Докажите, что задача о выборе путей является NР-полной.

10. Ваши друзья из фирмы WebExodus недавно консультировали компании с большими общедоступными сайтами (условия контракта не позволяют сказать, какими именно), и в ходе работы они столкнулись со следующей задачей стратегического размещения рекламы.

Компания предоставляет карту сайта, которая моделируется направленным графом G = (V, E). Компания также предоставляет множество t типичных маршрутов перемещения по сайту; маршруты моделируются направленными путями P₁, P₂, ..., P_t в графе G (то есть каждый маршрут P_i представляется путем в G). Компания хочет получить от WebExodus ответ на следующий вопрос: для заданного графа G, путей {P_i} и числа k возможно ли разместить рекламу не более чем на k узлах G, чтобы каждый путь P включал как минимум один узел с рекламой? Назовем эту задачу “задачей стратегического размещения рекламы” со входными данными G, {P_i: i = 1, ..., t} и k.

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

(a) Докажите, что задача стратегического размещения рекламы является NP-полной.

(b) Ваши друзья из WebExodus написали довольно быстрый алгоритм S, который выдает ответы “да/нет” для произвольного экземпляра задачи стратегического размещения рекламы. Будем считать, что алгоритм S всегда работает правильно.

Используя алгоритм S как “черный ящик”, разработайте алгоритм, который получает входные данные G, {P_i} и k из части (а) и делает одно из двух:

• выводит множество, содержащее не более k узлов из G, для которого каждый путь P_i содержит как минимум один такой узел, или

• выводит (обоснованно) сообщение о том, что такое множество из максимум k узлов не существует.

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

11. Как еще помнят некоторые (а другие слышали), идея гипертекста появилась за десятилетия до Всемирной паутины. Даже гипертекстовая литература появилась относительно давно: вместо линейной печатной страницы автор пишет историю, состоящую из набора связанных виртуальных мест, соединенных виртуальными “проходами”⁴. Таким образом, гипертекстовое произведение в действительности строится на основе направленного графа; для конкретности (хотя и с сужением полного диапазона возможностей) мы воспользуемся следующей моделью.

Будем рассматривать структуру гипертекстового произведения как направленный граф G = (V, E). Каждый узел u ∈ V содержит некоторый текст; когда читатель достигает u, он может выбрать любое ребро, ведущее из u; и если было выбрано ребро e = (u, v), читатель переходит к узлу v. Чтение начинается с узла s ∈ V и заканчивается на узле t ∈ V; когда читатель впервые достигает t, история завершается. Следовательно, любой путь от s к t является действительным сюжетом произведения. Учтите, что в отличие от просмотра страниц в браузере возможность возврата может отсутствовать; после перехода от u к v вы уже можете никогда не вернуться к u.

В такой модели гипертекстовая структура определяет огромное количество разных сюжетов с одним базовым контентом; и отношения между многочисленными вариантами порой становятся весьма нетривиальными. Пример задачи, встречающейся при таком подходе к структуре: рассмотрим фрагмент гипертекстового произведения на базе графа G = (V, E), в котором содержатся некоторые ключевые тематические элементы: любовь, смерть, война, стремление получить ученую степень по информатике и т. д. Каждый тематический элемент i представляется множеством T_i ⊆ V, состоящим из всех узлов G, в которых встречается данная тема. Теперь для заданного множества тематических элементов можно задать вопрос: существует ли действительное развитие сюжета, в котором встречается каждый из таких элементов? Конкретнее, для направленного графа G с начальным узлом s и конечным узлом t и тематическими элементами, представленными множествами T₁, T₂, ..., T_k, задача воплощения сюжета формулируется так: существует ли путь из s в t, содержащий по крайней мере один узел каждого из множеств T_i?

Докажите, что задача воплощения сюжета является NР-полной.

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

Существуют два простых способа управления доступом для бесплатных посетителей: (1) фиксированное подмножество страниц помечается как разрешенное для просмотра бесплатными посетителями или (2) просматриваться могут все страницы, но ограничивается максимальное количество страниц, которые могут просматриваться бесплатным посетителем за один сеанс. (Будем считать, что сайт может отслеживать действия посетителя на сайте.)

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

Формально сайт может моделироваться направленным графом G = (V, E), в котором ребра представляют веб-страницы, а ребра — направленные гиперссылки. Существует входной узел s ∈ V и зоны Z₁, ..., Z_k ⊆ V. Путь Р, выбираемый бесплатным пользователем, ограничивается включением одного узла из каждой зоны Z.

Один из недостатков усложненной политики доступа заключается в том, что с ней трудно ответить даже на самые простейшие вопросы относительно достижимости узлов, например: может ли бесплатный пользователь посетить заданный узел t? Более точная формулировка задачи проблемного пути выглядит так: для заданного графа G, Z₁, ..., Z_k, s ∈ V и конечного узла t ∈ V существует ли в G путь s-t, включающий не более одного узла из каждой зоны Z? Докажите, что задача проблемного пути является NР-полной.

13. Механизм комбинаторного аукциона был разработан экономистами для продажи множества объектов множеству потенциальных покупателей. (Федеральное агентство по связи США изучало эту разновидность аукционов для распределения радиочастот среди вещательных компаний.)

Простой пример комбинаторного аукциона: имеются n продаваемых объектов с метками I₁, ..., I_n. Каждый объект является неделимым и может быть продан только одному покупателю. Далее, m разных покупателей делают ставки: i-я ставка задает подмножество S_i объектов, а х_i — цена, которую покупатель готов заплатить за объекты множества S_i как за единое целое. (Ставка будет представляться парой (S_i, х).)

Теперь аукционист просматривает множество всех m заявок; он выбирает одни заявки и отклоняет другие. Каждый покупатель, ставка которого i будет принята, покупает все объекты соответствующего множества S_i. Следовательно, две принятые ставки не могут содержать множества, содержащие хотя бы один общий элемент, так как один объект не может быть продан двум разным людям. Аукционист получает сумму предложенных цен по всем принятым ставкам. (Обратите внимание: у каждого покупателя всего одна попытка, сделать новую ставку уже не получится.) Цель аукциониста — получить как можно больше денег.

Задача определения победителя для комбинаторного аукциона формулируется так: для заданных объектов I₁, ..., I_n, ставок (S₁, х₁), ..., (S_m, x_m) и границы B существует ли набор ставок, которые может принять аукционист, чтобы заработанная сумма была не меньше B?

Пример. Предположим, аукционист решает воспользоваться описанным методом для продажи лишнего компьютерного оборудования. Продаются четыре объекта: “PC”, “монитор”, “принтер” и “сканер”; трое покупателей делают ставки. Определяем:

S₁ = {PC, монитор}, S₂ = {PC, принтер}, S₃ = {монитор, принтер, сканер}

и

x₁ = х₂ = х₃ = 1

Сделаны ставки (S₁, х₁), (S₂, х₂) и (S₃, х₃), и граница B равна 2.

В данном экземпляре ответ будет отрицательным: аукционист сможет принять не более одной ставки (так как у любых двух ставок имеются общие объекты), поэтому общая выручка не может превысить 1.

Докажите, что задача определения победителя для комбинаторного аукциона является NР-полной.

14. Задача интервального планирования упоминалась в главах 1 и 4. Рассмотрим намного более сложную с вычислительной точки зрения ее разновидность, которую мы назовем задачей множественного интервального планирования. Как и прежде, имеется процессор, способный выполнять задания в течение некоторого периода времени (например, с 9:00 до 17:00).

Пользователи поставляют задания, которые должны выполняться на процессоре; в любой момент времени на процессоре может выполняться только одно задание. Однако в этой модели задания имеют более сложную структуру: каждое задание определяет множество интервалов, в течение которых ему требуется использовать процессоры. Итак, например, одно задание может занимать процессор с 10:00 до 11:00, а потом с 14:00 до 15:00. Если принять это задание, оно занимает процессор в течение двух часов, но вы можете принимать задания на другие периоды (включая промежуток с 11:00 до 14:00).

Имеется множество из n заданий, каждое из которых определяется множеством интервалов. Требуется найти ответ на следующий вопрос: для заданного числа k возможно ли принять не менее k заданий так, чтобы никакие два задания не перекрывались по времени?

Покажите, что задача множественного интервального планирования является NР-полной.

15. Однажды во время работы вам приносят пакет FedEx. В пакете лежит сотовый телефон, который начинает звонить, — оказывается, это ваш друг Нео, от которого уже давно не было никаких известий. Все разговоры с Нео всегда проходят одинаково: сначала он долго и пафосно объясняет, почему он обратился к вам, но в итоге все сводится к просьбам потратить ваше время на то, чтобы помочь ему с решением некоторой проблемы.

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

• множество L из m мест, в которых могут быть размещены датчики;

• множество S из b источников помех, каждый из которых блокирует некоторые частоты в некоторых местах. А конкретно каждый источник помех i задается парой (F_i, L_i), где F_i — подмножество частот, а L_i — подмножество мест; это означает, что датчик, помещенный в любое из мест множества L_i, не сможет получать сигналы на любых частотах множества F_i (из-за воздействия помех).

Подмножество L' ⊆ L мест называется достаточным, если для каждой из n частот j существует некоторое место в L', в котором частота j не блокируется ни одним источником помех. Тогда, размещая датчик в каждом месте достаточного множества, вы сможете успешно отслеживать все n частот.

У соратников Нео есть k датчиков, и они хотят узнать, существует ли достаточное множество мест с размером не более k. Назовем следующую формулировку задачей отслеживания частот: для заданных частот, мест, источников помех и параметра к существует ли достаточное множество с размером не более k?

Пример. Допустим, заданы четыре частоты {f₁,f₂,f₃,f₄} и четыре места {l₁,l₂,l₃,l₄}. Существуют три источника помех:

(F₁,L₁) = ({f₁,f₂}, {l₁,l₂,l₃})

(F₂,L₂) = ({f₃,f₄}, {l₃,l₄})

(F₃,L₃) = ({f₂,f₃}, {l₁})

В этой ситуации существует достаточное множество с размером 2: можно выбрать места l₂ и l₄. (Так как f₁ и f₂ не блокируются в l₄, a f₃ и f₄ не блокируются в l₂.)

Докажите, что задача отслеживания частот является NР-полной.

16. Рассмотрим задачу характеристики множества по размерам его пересечений с другими множествами. Имеется конечное множество U размера n, а также набор A₁, ..., A_m подмножеств U. Также заданы числа c₁, ..., c_m. Вопрос звучит так: существует ли такое множество X ⊂ U, что для всех i = 1, 2, ..., m мощность X ∩ А. равна с? Назовем его задачей выведения пересечений с входными данными U, {А_i} и {с_i}.

Докажите, что задача выведения пересечений является NР-полной.

17. Задан направленный граф G = (V, E) с весами w_e ребер e ∈ E. Веса могут быть отрицательными или положительными. В задаче цикла с нулевым весом требуется решить, существует ли в Gпростой цикл, сумма весов ребер которого равна 0. Докажите, что эта задача является NР-полной.

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

Состав комитета представлен множеством M = {m₁, ..., m_n} из n членов. За последний год в комитете проводилось голосование по t разным вопросам. По каждому вопросу каждый член комитета мог проголосовать “За”, “Против” или “Воздержаться”. В результате комитет принимает положительное решение по каждому вопросу, если количество голосов “За” строго превышает количество голосов “Против” (воздержавшиеся не считаются ни за одну из сторон); в противном случае принимается отрицательное решение.

Имеется большая таблица, содержащая данные голосования каждого участника комитета по каждому вопросу. Рассматривается следующее определение: подмножество членов M' ⊆ Mназывается решающим, если при проверке только голосов, поданных членами M', решение комитета по каждому вопросу будет тем же. (Иначе говоря, результат голосования членов M' по каждому вопросу определяет общий результат голосования всего комитета.) Такое подмножество можно рассматривать как своего рода “ближнее окружение”, которое отражает мнение комитета в целом.

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

Пример. Допустим, имеются четыре члена комитета и три вопроса. Мы ищем решающее подмножество с размером не более k = 2, а голосование проходило так:

Вопрос		m2	m3	m4
Вопрос 1	За	За	Воздержаться	Против
Вопрос 2	Воздержаться	Против	Против	Воздержаться
Вопрос 3	За	Воздержаться	За	За

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

Докажите, что задача решающего подмножества является NР-полной.

19. Предположим, вы консультируете управление порта в маленькой стране на побережье Тихого океана. Ежегодный объем сделок исчисляется миллиардами, и доход ограничивается исключительно скоростью разгрузки кораблей, прибывающих в порт.

Работа с опасными грузами усложняет и без того непростую задачу. Допустим, утром в порт прибывает морской конвой, который привозит n контейнеров с разными видами опасных материалов. В доке стоят m машин, каждая из которых вмещает до k контейнеров.

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

• Алгоритм с полиномиальным временем для решения задачи.

• Доказательство NР-полноты задачи.

(a) Для каждого контейнера существует заданное подмножество машин, на которых они могут перевозиться. Возможно ли погрузить все n контейнеров на m машин, чтобы ни одна машина не была перегружена, а каждый контейнер был погружен на машину, для которой разрешена его перевозка?

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

20. Существует много разных способов формального представления задачи кластеризации, целью которой является разбиение набора объектов на “похожие” группы. Естественным способом представления входных данных для задачи кластеризации является множество объектов p₁, p₂, ..., p_n, в котором для каждой пары определяется числовое расстояние d(p_i, p_j). (Для расстояний устанавливаются требования: d(p_i, p_j) = 0; d(p_i, p_j) > 0 для разных p_i и p_j и симметричность d(p_i, p_j) = d(p_j, p_i).)

Ранее в разделе 4.7 была рассмотрена одна из возможных формулировок задачи кластеризации: разбить объекты на k множеств так, чтобы максимизировать минимальное расстояние между парами объектов из разных кластеров. Как выясняется, задача решается удачным применением задачи о минимальном остовном дереве.

Другой, но на первый взгляд похожий способ формализации может выглядеть следующим образом: разбить объекты на k множеств так, чтобы минимизировать максимальное расстояние между любой парой объектов в пределах одного кластера. Обратите внимание на отличия: если в формулировке из предыдущего абзаца нужно было найти кластеры, среди которых не было бы двух “слишком близких”, в новой формулировке кластеры не должны быть слишком “широкими”, то есть ни один кластер не должен содержать двух точек, находящихся на большом расстоянии друг от друга.

Тот факт, что новая формулировка обладает слишком большой вычислительной сложностью для оптимального решения, может показаться удивительным (при таком сходстве задач). Чтобы задачу можно было проанализировать в контексте NР-полноты, сначала запишем ее в формулировке с принятием решения. Для заданных n объектов p₁, p₂, ..., p_n с расстояниями, определенными выше, и границы B задача кластеризации малого диаметра формулируется следующим образом: возможно ли разбить объекты на к множеств так, чтобы расстояние между любыми двумя точками, принадлежащими одному множеству, не превышало B?

Докажите, что задача кластеризации малого диаметра является NР-полной.

21. После знакомства с популярной книгой для начинающих предпринимателей вы осознаете, что компьютерная система в вашем офисе нуждается в обновлении. Однако это начинание сталкивается с некоторыми непростыми проблемами. При планировании новой системы необходимо выбрать k компонентов: операционная система, редактор текстов, почтовый клиент и т. д. Для j-го компонента системы существует множество A_j вариантов; а конфигурация системы состоит из выбора одного элемента из каждого из множеств A₁, A₂, ..., A_k.

Проблемы возникают из-за того, что некоторые пары вариантов из разных множеств оказываются несовместимыми. Вариант x_i ∈ A_i и вариант x_j ∈ A_j образуют несовместимую пару, если они не могут содержаться в одной системе: например, Linux (вариант операционной системы) и Microsoft Word (вариант редактора текстов) образуют несовместимую пару. Конфигурация системы называется полностью совместимой, если она состоит из элементов x₁ ∈ A₁, x₂ ∈ A₂, ... x_k ∈ A_k , из которых ни одна пара (x_i, x_j) не является несовместимой. Теперь мы можем определить задачу полностью совместимой конфигурации. Экземпляр такой задачи состоит из непересекающихся множеств вариантов A₁, A₂, ..., A_k, и множества P несовместимых пар (x,y), в котором x и у являются элементами разных множеств вариантов. Требуется решить, существует ли полностью совместимая конфигурация: выбор элемента из каждого множества вариантов, при котором ни одна пара выбранных элементов не принадлежит множеству P.

Пример. Допустим, k = 3, а множества A₁, A₂, A₃ обозначают варианты выбора операционной системы, редактора текстов и почтового клиента соответственно:

Множество несовместимых пар выглядит так:

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

22. Предположим, вы получили алгоритм A — “черный ящик”, который получает ненаправленный граф G = (V, E) и число k и ведет себя следующим образом:

• Если граф G не является связным, алгоритм просто возвращает сообщение о несвязности.

• Если граф G является связным и в нем есть независимое множество с размером не менее k, алгоритм возвращает сообщение “Да”.

• Если граф G является связным, но в нем нет независимого множества с размером не менее k, алгоритм возвращает сообщение “Нет”.

Предположим, алгоритм A выполняется за время, полиномиальное по размеру G и k.

Покажите, как с использованием обращений к A решить за полиномиальное время задачу о независимом множестве: для заданного графа G и числа k содержит ли граф G независимое множество с размером не менее k?

23. Для множества конечных двоичных строк S= {s₁, s_k} строка и называется конкатенацией по S, если она равна s_i1, s_i2, ..., s_ik для некоторых индексов i₁, ..., i_l ∈ {1, ..., k}. Ваш знакомый рассматривает следующую задачу: для заданных двух множеств конечных двоичных строк A = {a₁, ..., a_m} и B = {b₁, ..., b_n} существует ли строка u, которая бы одновременно являлась конкатенацией по A и конкатенацией по B? Ваш знакомый заявляет: “По крайней мере задача принадлежит NP, поскольку для доказательства положительного ответа мне достаточно предъявить такую строку u”. Вы указываете (разумеется, вежливо), что такое объяснение совершенно несостоятельно: как узнать, что кратчайшая из таких строк и не имеет длины, экспоненциальной по размеру входных данных, — ведь в этом случае она не может служить сертификатом полиномиального размера?

Но как выясняется, это заявление можно преобразовать в доказательство принадлежности NP. А именно, докажите следующее утверждение:

Если существует строка и, которая является конкатенацией и по A, и по B, то существует строка, длина которой ограничивается полиномиально по сумме длин строк в A U B.

24. Имеется двудольный граф G = (V, E); допустим, его узлы разбиты на множества X и Y так, что один конец каждого ребра принадлежит X, а другой принадлежит Y. Определим (а, b)-скелет графа G как множество ребер E' ⊆ E, для которого не более а узлов в X инцидентно ребру в E' и не менее b узлов в Y инцидентно ребру в E'.

Покажите, что для заданного двудольного графа G и чисел а и b задача принятия решения о существовании (а, b)-скелета является NP-полной.

25. Для функций g₁, ..., g_l функция max(g₁, ..., g_l) определяется по формуле

Рассмотрим следующую задачу: имеется n кусочно-линейных непрерывных функций f₁, ..., f_n, определенных на интервале [0, t] для некоторого целого t. Также задано целое число В. Требуется решить: существуют ли k функций t_t1, ..., f_tk, для которых

Докажите, что эта задача является NP-полной.

26. Разъезжая по отдаленным частям света, вы со своим другом накопили большую груду сувениров. В то время вы не задумывались над тем, какие сувениры останутся вам, а какие — ему, но, похоже, пришло время разделить приобретения. Один из возможных способов дележа выглядит так: допустим, имеется n объектов 1, 2, ..., n и объект i имеет согласованную ценность х_i. (Например, это может быть сумма, за которую его можно продать; будем считать, что у вас с друзьями нет расхождений по поводу оценки). Можно попытаться найти разбиение объектов на два множества, чтобы общая ценность объектов в каждом множестве была одинаковой.

Для этого следует решить следующую задачу численного разбиения. Даны положительные целые числа х₁, ..., x_n; требуется решить, возможно ли разбить числа на два множества S₁ и S₂ с одинаковой суммой:

Покажите, что задача численного разбиения является NP-полной.

27. Рассмотрим следующую задачу. Даны положительные целые числа x₁, ..., x_n, а также числа k и B. Требуется узнать, возможно ли разбить числа {x_i} на k множеств S₁, ..., S_k так, чтобы квадраты сумм множеств в совокупности давали не более B:

Покажите, что эта задача является NР-полной.

28. Ниже описана разновидность задачи о независимом множестве. Имеется граф G = (V, E) и целое число к. В контексте этой задачи множество I ⊂ V будет называться строго независимым, если для любых двух узлов v, u ∈ I ребро (v, u) не принадлежит E, а также не существует пути из двух ребер из u в v — то есть не существует узла w, для которого (u, w) ∈ E и (w, v) ∈ E. Задача о строго независимом множестве требует решить, существует ли в G строго независимое множество с размером не менее k.

Докажите, что задача о строго независимом множестве является NР-полной.

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

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

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

Задача о доминирующем множестве формулируется следующим образом: для заданной сети G и числа k возможно ли разместить k копий базы данных в k разных узлах так, чтобы каждый узел либо содержал собственную копию базы данных либо был соединен прямым каналом с узлом, содержащим копию? Покажите, что задача о доминирующем множестве является NР-полной.

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

Для примера рассмотрим традиционную задачу минимизации функции одной переменной — допустим, f (x) = 3 + x - 3х² на интервале x ∈ [0,1]. Производная равна нулю в точке x = 1/6, но это точка максимума, а не минимума функции; чтобы получить минимум, следует выполнить стандартную проверку значений на границах интервала (причем минимум в данном случае достигается на границе x = 1).

Проверка границы не создает серьезных проблем для функций одной переменной; но предположим, что в задаче требуется минимизировать функцию n переменных x₁, x₂, ..., x_n на единичном кубе, где все x₁, x₂, ..., x_n ∈ [0,1]. Минимум может достигаться как внутри куба, так и на его границах; и последняя перспектива выглядит устрашающе, так как куб состоит из 2ⁿ “углов” (для которых каждое из значений x. равно либо 0, либо 1), а также из различных фрагментов других измерений. Из-за этой сложности книги по матанализу подозрительно нечетко излагают этот вопрос при описании многофакторных задач оптимизации.

И тому есть веская причина: минимизация функции с n переменными в единичном n-мерном кубе относится к классу NР-полных задач. Чтобы это утверждение стало более конкретным, рассмотрим специальный случай многочленов с целочисленными коэффициентами по n переменным x₁, x₂, ..., x_n. На всякий случай освежим в памяти терминологию: одночленом называется произведение вещественного коэффициента с и каждой из переменных х., возведенной в неотрицательную целую степень а.; это можно записать в виде (Например, 2x₁²x₂x₃⁴является одночленом). Многочленом называется сумма конечного набора одночленов (например, 2x₁²x₂x₃⁴ + x₁x₃ – 6x₂²x₃² является многочленом).

Задача минимизации многофакторного многочлена формулируется так: для заданного многочлена по n переменным с целочисленными коэффициентами и заданной целой границей B возможно ли выбрать вещественные числа x₁, x₂, ..., x_n ∈ [0, 1], с которыми многочлен достигает значения ≤ B?

Выберите в этой главе задачу Y, которая заведомо является NР-полной, и покажите, что Y ≤_р Минимизация многофакторного многочлена.

31. Для заданного ненаправленного графа G = (V, E) множеством обратной связи называется множество X ⊆ V, обладающее тем свойством, что G-X не содержит циклов. Задача ненаправленного множества обратной связи формулируется так: для заданных G и k содержит ли G множество обратной связи с размером не более k? Докажите, что задача ненаправленного множества обратной связи является NР-полной.

32. Расшифровка генома сопряжена с множеством сложных вычислительных задач. На простейшем уровне каждая хромосома организма может рассматриваться как чрезвычайно длинная строка (возможно, состоящая из миллионов символов) четырехбуквенного алфавита {A, C, G, T}. Один из классов методов расшифровки генома базируется на генерировании большого количества коротких, перекрывающихся фрагментов хромосомы, с последующим построением полной длинной строки, представляющей хромосому, из этого набора перекрывающихся подстрок.

Хотя мы не будем рассматривать задачи сборки строк во всех подробностях, ниже приведена упрощенная задача, которая дает некоторое представление о вычислительной сложности задач этой области. Допустим, имеется множество S = {s₁, s₂, ..., s_r} коротких строк ДНК из q-буквенного алфавита; каждая строка s₁ имеет длину 2l для некоторого числа l ≤ 1. Также имеется библиотека дополнительных строк Т = {t₁, t₂, ..., t_m} из символов того же алфавита; каждая из этих строк также имеет длину 2l. Пытаясь определить, может ли строка s_b следовать прямо за строкой s_a в хромосоме, мы проверяем, содержит ли библиотека Т строку t_k, чтобы первые l символов t_k совпадали с последними l символами в s_a, а последние l символов t_k совпадали с первыми l символами в s_b. Если это возможно, мы говорим, что t_k скрепляет пару (s_a, s_b). (Другими словами, t_k может быть фрагментом ДНК, “перекрывающим” точку перехода s_a в s_b.)

Нам хотелось бы сцепить все строки S в некотором порядке без перекрытий, так чтобы каждая последовательная пара скреплялась некоторой строкой из библиотеки Т. Следовательно, мы хотим упорядочить строки S в виде s_i1, s_i2, ..., s_in, где i₁, i₂, ..., i_n — такая перестановка {1, 2, ..., n}, что для всех j = 1, 2, ..., n-1 существует строка t_k, скрепляющая пару (Одна строка t_kможет использоваться для нескольких последовательных пар в конкатенации.) Если это возможно, говорят, что у множества S существует идеальная сборка.

Для заданных множеств S и T задача об идеальной сборке формулируется так: существует ли для S идеальная сборка по отношению к T? Докажите, что задача об идеальной сборке является NР-полной.

Пример. Допустим, задан алфавит {A,C,G,T}, множество S = {AG,TC,TA} и множество Т= {AC,CA,GC,GT} (так, что каждая строка имеет длину 2l = 2). Тогда ответ на этот экземпляр задачи об идеальной сборке будет положительным: три строки S можно сцепить в порядке TCAGTA (так, что ). В этом порядке пара скрепляется строкой СА из библиотеки Т, а пара сцепляется строкой GT из библиотеки Т.

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

Для моделирования этих сложностей мы введем концепцию ценности, которая назначается каждым человеком каждому объекту в реальном мире. Предположим, имеется множество из n людей p₁, ..., p_n и множество m объектов a₁, ..., a_m. Каждый объект принадлежит одному человеку. Далее, у каждого человека р_i имеется оценочная функция v_i, которая определяется так, что v_i (a_j) является неотрицательным числом, которое определяет ценность объекта а_j для р_i, — чем больше число, тем большую ценность объект представляет для человека.

Обмен между двумя людьми в такой системе возможен в том случае, если существуют люди р_i и р_j, и подмножества объектов A_i и A_j, принадлежащих p_i и р_j соответственно, так что для каждого участника предпочтительными являются объекты того подмножества, которое ему пока не принадлежит. А точнее, суммарная ценность объектов A_j для участника р_i превышает суммарную ценность объектов A_i, и суммарная ценность объектов A_i для участника р_j превышает суммарную ценность объектов A_j. (Обратите внимание: подмножество A_i не обязано включать все объекты, принадлежащие р_i; то же относится к A_j.) A_i и A_j могут быть произвольными подмножествами принадлежащих им объектов, удовлетворяющим этим критериям.)

Допустим, вы получили экземпляр задачи натурального обмена, определяемый приведенными выше данными ценности объектов (чтобы избежать проблем с представлением вещественных чисел, будем считать, что ценности всех объектов представляют собой натуральные числа). Докажите, что задача определения возможности обмена между двумя людьми является NР-полной.

34. В 1970-е годы ученые, работающие в области математической социологии (включая Марка Грановеттера и Томаса Шеллинга), взялись за разработку моделей некоторых видов коллективного человеческого поведения: почему одни модные “фишки” приживаются, а другие быстро отмирают? Почему одни технологические новшества распространяются повсеместно, а другие не выходят за пределы малых групп пользователей? Какова динамика беспорядков и грабежей, которые иногда проявляются в поведении разъяренной толпы? Ученые предположили, что все эти ситуации являются примерами каскадных процессов, при которых поведение участника сильно зависит от поведения его близкого окружения; процесс, запущенный несколькими участниками, распространяется на все большее количество людей и в конечном итоге получает очень широкое воздействие. Этот процесс можно сравнить с распространением слухов или эпидемии, передаваемой от человека к человеку.

Рассмотрим простейшую версию модели каскадных процессов. Имеется некоторое поведение (собирание марок, покупка сотового телефона, участие в беспорядках), и в какой-то момент времени каждый человек либо принимает в нем участие, либо не принимает. Население представляется направленным графом G = (V, E), в котором узлы соответствуют людям, а ребро (v, w) означает, что человек v влияет на поведение человека w; если человек v участвует в поведении, это также способствует принятию поведения человеком w. У каждого человека w также имеется порог θ(w) ∈ [0,1], который имеет следующий смысл: в любой момент, когда доля узлов, от которых выходят ребра в w, достигнет по меньшей мере θ(w), узел w также начинает участвовать в поведении.

Узлы с низким порогом быстрее “заражаются” поведением, узлы с более высоким порогом более консервативны. Узел w с порогом θ(w) = 0 принимает поведение немедленно, без влияния окружения. Наконец, нужно договориться по поводу узлов без входящих ребер: будем считать, что они принимают поведение, если θ(w) = 0, и не принимают его при более высоком пороге.

Для заданного экземпляра этой модели распространение поведения может быть смоделировано следующим образом.

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

В последние годы исследователи, работающие в области маркетинга и анализа данных, изучали возможность применения этой модели для анализа эффектов “сарафанного радио” в успехе новых продуктов (так называемый вирусный маркетинг). Под поведением понимается использование нового продукта; нужно попытаться убедить нескольких ключевых представителей населения опробовать новый продукт и надеяться, что это вызовет по возможности значительный каскадный эффект.

Допустим, выбирается множество узлов S ⊆ V, а порог каждого узла в S обнуляется 0. (Убедив людей опробовать новый продукт, мы гарантируем их участие.) Затем запускается описанный выше процесс, и мы смотрим, насколько большим окажется итоговое множество участников. Обозначим размер итогового множества участников f(S) (размер записывается в виде функции от S, так как он естественно зависит от выбора S). Величина f(S) может рассматриваться как влияние множества S, так как она отражает распространение поведения, “посеянного” в S.

При планировании маркетинговой кампании целью является нахождение малого множества S, имеющего как можно большее влияние f(S). Задача максимизации влияния определяется так: для заданного направленного графа G = (V, E) с пороговыми значениями для каждого узла, параметров к и b существует ли множество S, содержащее не более к узлов, для которых f(S) ≥ b?

Докажите, что задача максимизации влияния является NР-полной.

Пример. Допустим, граф G = (V, E) состоит из пяти узлов {a, b, c, d, e}, четырех ребер (a, b), (b, c), (e, d), (d, c), а пороги всех узлов установлены равными 2/3. В этом случае ответ на экземпляр задачи максимизации влияния, определяемой графом G, с k = 2 и b = 5, будет положительным: если выбрать S = {a, e}, то все три остальных узла также станут участниками. (В этой задаче такой вариант выбора S только один; например, если выбрать S = {a, d}, то b и c станут участниками, но e не станет; а если выбрать S = {a, b}, то ни один из узлов c, d или e не станет участником.)

35. Трое ваших друзей работают в крупной компании, занимающейся компьютерными играми. Вот уже несколько месяцев они работают над идеей новой игры “Droid Trader!”, одобренной руководством компании. За это время им пришлось выслушать множество обескураживающих замечаний, от “Вам придется основательно поработать с отделом маркетинга над названием” до “А может, стоит добавить побольше крови?”

Но сейчас практически все уверены, что игра пойдет в производство, и друзья обращаются к вам за решением последней проблемы: а не получится ли игра слишком простой — игроки слишком быстро освоят ее и им станет скучно?

Вы не сразу разбираетесь в происходящем по их подробному описанию; но если отбросить все космические сражения, поединки и псевдомистицизм в духе “Звездных войн”, основная идея выглядит так. Игрок управляет космическим кораблем и пытается заработать деньги, покупая и продавая дроидов на разных планетах. Всего существуют n типов дроидов и k планет. Каждая планета p обладает следующими свойствами: на ней продаются s(j, p) ≥ 0 дроидов типа j по фиксированной цене x(j, p) ≥ 0 за штуку, для всех j = 1, 2, ..., n; также существует спрос на d(j, p) ≥ 0 дроидов типа j по фиксированной цене y(j, p) ≥ 0. (Будем считать, что на планете не может быть положительного спроса одновременно с положительным предложением на дроидов одного типа; таким образом, по крайней мере одно из значений s(j, p) и d(j, p) равно 0.)

Игрок начинает на планете s с z единицами денег и заканчивает на планете t; существует направленный ациклический граф G для множества планет, в котором пути s-t соответствуют действительным маршрутам игрока. (Граф G выбран ациклическим, чтобы избежать бесконечных игр.) На протяжении пути s-t P в G игрок может участвовать в сделках следующим образом. Прибывая на планету p в пути P, он может купить до s(j, p) дроидов типа j по цене x(j, p) за штуку (при условии, что у него хватит денег) и/или продать до d(j, p) дроидов типа j по цене y(j, p) за штуку (дляj = 1, 2, ..., n). Счет игрока определяется суммой денег, которую он имеет на руках при прибытии на планету t. (Также начисляются дополнительные очки за космические сражения и поединки, но для формулировки задачи они нас не интересуют.)

Итак, задача фактически сводится к получению наибольшего результата. Другими словами, для заданного экземпляра игры с направленным ациклическим графом G на базе множества планет, всех остальных параметров, описанных выше, и целевого ограничения B существует ли путь P в G и последовательность сделок в P, при которой игрок заканчивает со счетом не менее B? Назовем этот экземпляр задачей максимального счета в игре Droid Trader!, или сокращенно 3MCDT!.

Докажите, что задача 3MCDT! является NP-полной (в предположении P ≠ NP). Тем самым вы гарантируете отсутствие простой стратегии для получения высокого счета в игре ваших друзей.

36. Даже если вы знаете людей много лет, понять их порой бывает нелегко. Для примера возьмем хотя бы Раджа и Аланис. Ни один из них не относится к “жаворонкам”, но сейчас они ежедневно встают в 6 утра и отправляются на рынок за свежими фруктами и овощами для своего ресторана здорового питания.

Стремясь сэкономить на продуктах, они столкнулись с непростой проблемой. Существует большое множество из n ингредиентов I₁, I₂, ..., I_n (пучки зелени, бутылки рисового уксуса и т. д.). Ингредиент I_j покупается в единицах по s(j) граммов (с покупкой целого количества единиц) и стоит c(j) долларов за единицу. Кроме того, он остается годным для использования в течение t(j) дней с даты покупки.

За следующие к дней ваши друзья должны подать k фирменных блюд, по одному в день. (Выбор дня, в который должно готовиться то или иное блюдо, остается на их усмотрение.) Фирменное блюдо с номером i использует подмножество S_i ⊆ {I₁, I₂, ..., I_n} ингредиентов, а именно a(I,j) граммов ингредиента I_j. Наконец, существует еще одно ограничение: постоянные клиенты ресторана останутся постоянными только в том случае, если они получают еду, приготовленную из самых свежих продуктов. Для каждого фирменного блюда ингредиенты S_i делятся на два подмножества: те, которые должны покупаться в день изготовления фирменного блюда, и те, которые могут быть куплены в любой день, но их срок годности еще не истек. (Например, салат-месклан с базиликом должен готовиться из базилика, купленного в этот же день, а в соусе песто с рукколой, базиликом и корнелльским козьим сыром можно использовать базилик, купленный несколько дней назад, если он еще не завял).

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

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

Докажите, что задача планирования фирменных блюд является NР-полной.

37. Как ни странно, даже в “Звездных войнах” кроется немало NР-полных задач. Рассмотрим задачу, с которой столкнулись Люк, Лея и их друзья на пути со “Звезды Смерти” на скрытую базу повстанцев. Галактику можно рассматривать как ненаправленный граф G = (V, E), в котором узлы представляют звездные системы, а ребро (u, v) обозначает возможность прямого перемещения из u в v. “Звезде Смерти” соответствует узел s, а скрытой базе повстанцев — узел t. Расстояния, представленные ребрами графа, не одинаковы; каждому ребру е назначается целочисленная длина l_e ≥ 0. Кроме того, некоторые ребра представляют маршруты, активно патрулируемые имперскими кораблями; соответственно каждому ребру e также назначается целочисленный риск r_e≥ 0, который определяет прогнозируемые повреждения от насыщенных спецэффектами космических сражений в случае перемещения по этому ребру.

Самый безопасный маршрут пролегает по дальним секторам Галактики, от одной безопасной звездной системы к другой; но в этом случае топливо у корабля кончится задолго до того, как он доберется до места назначения. Самый быстрый маршрут — рвануть через населенный центр, но тогда придется отбиваться от слишком большого количества имперских кораблей. В общем случае общая длина любого пути Р из s в t определяется как сумма длин всех его ребер, а общий риск — как сумма рисков всех его ребер.

Итак, Люк, Лея и компания пытаются решить для этого графа усложненную разновидность задачи о кратчайшем пути: им нужно добраться из s в t по пути с разумно малой общей длиной и общим риском. А конкретнее задачу о кратчайшем галактическом пути можно сформулировать так: для заданной конфигурации, описанной выше, и целочисленных ограничений L и Rсуществует ли путь из s в t, в котором общая длина не превышает L и при этом общий риск не превышает R?

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

38. Рассмотрим разновидность задачи о дереве Штейнера, которую мы будем называть графическим деревом Штейнера. Имеется ненаправленный граф G = (V, E), множество вершин X ⊆ V и число k. Требуется решить, существует ли множество F ⊆ E, содержащее не более k ребер, для которого в графе (V, F) X принадлежит одной компоненте связности.

Покажите, что задача о графическом дереве Штейнера является NР-полной.

39. Задача о направленных непересекающихся путях определяется следующим образом: имеется направленный граф G и k пар узлов (s₁, t₁), (s₂, t₂), ..., (s_k, t_k). Требуется решить, существуют ли непересекающиеся по узлам пути Р₁, Р₂, ..., Р_k, такие, что Р_i идет из s_i в t_i.

Покажите, что задача о направленных непересекающихся путях является NР-полной.

40. Рассмотрим задачу, встречающуюся при проектировании схем широковещательной рассылки в сети. Имеется направленный граф G = (V, E) с узлом r ∈ V и назначенным множеством “целевых узлов” T ⊆ V - {r}. С каждым узлом v связано время переключения s_v, которое представляет собой положительное целое число.

Во время 0 узел r генерирует сообщение, которое должно быть получено каждым узлом в T. Для этого нужно построить схему, в которой r передает информацию некоторым из своих соседей (последовательно), которые в свою очередь сообщают некоторым из своих соседей и т. д., пока сообщение не будет получено каждым узлом T. На более формальном уровне схема рассылки определяется следующим образом: узел r может отправить копию сообщения одному из своих соседей во время 0; сосед получит сообщение во время 1. В общем случае во время t ≥ 0 любой узел v, уже получивший сообщение, может отправить копию сообщения одному из своих соседей — при условии, что он еще не отправлял копию сообщения в любой из моментов t - s_v + 1, t - s_v + 2, ..., t - 1. (В этом проявляется роль времени переключения: v необходима пауза в s_v - 1 шагов между последовательными отправками сообщения. Если s_v = 1, никакие дополнительные ограничения не добавляются.)

Временем завершения схемы рассылки называется минимальное время t, к которому все узлы T получат сообщение. Задача о времени рассылки определяется так: для входных данных, описанных выше, и границы b существует ли схема рассылки с временем завершения, не превышающим b?

Докажите, что задача о времени рассылки является NР-полной.

Пример. Допустим, имеется направленный граф G = (V, E) с множеством V = {r, a, b, c} и ребрами (r, a), (a, b), (r, c); множество T = {b, c} и время переключения составляет s_v = 2 для всех v ∈V. В этом случае схема рассылки с минимальным временем завершения будет выглядеть так: r отправляет сообщение a во время 0; а отправляет сообщение b во время 1; r отправляет сообщение c во время 2; схема завершается во время 3, когда c получает сообщение. (Обратите внимание: узел a может отправить сообщение при получении его во время 1, так как это его первая отправка сообщения; но узел r не может отправить сообщение во время 1, так как s_r = 2, а сообщение было отправлено во время 0.)

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

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

(b) Предположим, каждый цикл должен содержать не менее трех ребер. Покажите, что проверка существования такого циклического покрытия для графа G является NР-полной.

42. Компания, занимающаяся проектированием коммуникационных сетей, обращается к вам со следующей задачей. Изучается конкретная сеть, состоящая из n узлов и моделируемая направленным графом G = (V, E). По соображениям отказоустойчивости G требуется разбить на максимально возможное количество виртуальных “доменов”: доменом в G называется множество X узлов с размером не менее 2, так что для каждой пары узлов u, v ∈ X существуют направленные пути из и в v и из v в u, полностью содержащиеся в X.

Покажите, что следующая задача доменной декомпозиции является NР-полной. Имеется направленный граф G = (V, E) и число k; возможно ли разбить V не менее чем на k множеств, каждое из которых является доменом?

Примечания и дополнительная литература

В примечаниях к главе 2 упоминаются некоторые ранние работы по формализации вычислительной эффективности при полиномиальном времени; концепция NР-полноты сформировалась на основе этих работ и заняла центральное место в вычислительной теории после работ Кука (Cook, 1971), Левина (Levin, 1973) и Карпа (Karp, 1972). Эдмондс (Edmonds, 1965) обратил особое внимание на класс задач NP ∩ co-NP — то есть задач, обладающих “хорошей характеризацией”. В его статье также содержится явно сформулированная гипотеза о том, что задача коммивояжера не решается за полиномиальное время, что можно считать предварительной формулировкой гипотезы P ≠ NP. У Сипсера (Sipser, 1992) приводится полезное описание всего исторического контекста.

Книга Гэри и Джонсона (Garey, Johnson, 1979) предоставляет обширный материал по NP-полноте и завершается очень полезным каталогом известных NP- полных задач. Хотя в этом каталоге по понятным причинам присутствуют только задачи, известные на момент публикации книги, он остается очень полезным справочником для новых задач, которые могут оказаться NP-полными. В настоящее время пространство известных NP-полных задач продолжает стремительно расширяться; как сказал Кристос Пападимитриу в своей лекции, “ежегодно публикуется около 6000 статей, результатом которых является вывод о NP-полноте. Это означает, что после обеда была обнаружена новая NP-полная задача” (лекция проводилась в 14:00).

NP-полноту можно интерпретировать как утверждение о том, что в каждой отдельной NP-полной задаче кроется полная сложность NP. У этого факта имеется конкретное отражение: некоторым NP-полным задачам, рассматриваемым здесь, были посвящены целые книги; задача коммивояжера рассматривается у Лоулера и др. (Lawler, 1985); задача о раскраске графа является темой книги Дженсена и Тофта (Jensen, Toft, 1995); задаче о рюкзаке посвящена книга Мартелло и Тота (Martello, Toth, 1990). NP-полнота задач планирования обсуждается в обзоре Лоулера и др. (Lawler, 1993).

Примечания к упражнениям

Некоторые упражнения демонстрируют другие хрестоматийные задачи, встречавшиеся в ходе изучения NP-полноты; в частности, это упражнения 5, 26, 29, 31, 38, 39, 40 и 41. Упражнение 33 основано на обсуждении с Дэниелом Головиным, а в упражнении 34 используются результаты нашей работы с Дэвидом Кемпе. Упражнение 37 является примером задач о кратчайшем пути с двумя критериями; это конкретное применение было предложено Мэвериком Ву.

---

¹ Операция поиска строки t, с которой эффективный сертифицирующий алгоритм примет ввод s, часто рассматривается как недетерминированный поиск по пространству возможных доказательств t; по этой причине термин NP был выбран как сокращение для “Nondeterministic Polynomial time” (“недетерминированное полиномиальное время”).

² Этот аргумент дает представление о том, как был получен этот подграф. Цель заключается в том, чтобы верхний узел не мог получить никакой цвет. Мы начинаем с “присоединения” трех узлов, соответствующих литералам (все из которых окрашены в цвет False), в нижнем ряду. Затем для каждого узла мы продвигаемся вверх и ставим его в пару с узлом известного цвета, чтобы узлу сверху достался третий цвет. Продолжая таким образом, мы придем к узлу, которому гарантированно будет назначен нужный цвет. Соответственно мы форсируем назначение трех разных цветов, начиная с трех разных литералов, а затем подводим все три разноцветных узла к верхнему узлу, создавая ситуацию с невозможностью назначения цвета.

³ “The New Yorker”, 16 августа 1999 года.

⁴ Например, см. http://www.eastgate.com.