Упражнения с решениями - Расширение пределов разрешимости

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

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

А именно, для заданного множества булевых переменных X = {х₁, х₂, ..., x_n} неполным присваиванием для X называется присваивание значения 0, 1 или ? каждому х_i; другими словами, это функция ρ: X → {0, 1, ?}. Переменная х_i называется определенной неполным присваиванием, если она получает значение 0 или 1, и неопределенной, если она получает значение ?. Фактически неполное присваивание выбирает значение 0 или 1 для каждой из определенных переменных, а переменные со значением ? остаются неопределенными.

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

Предположим, заданы условия

Тогда неполное присваивание, которое задает х₁ = 1, х₃ = 0, а всем остальным переменным значение ?, имеет только две определенные переменные, но обеспечивает выполнение набора условий: как бы ни были заданы остальные четыре переменные, условия будут истинными.

Это определение можно формализовать. Вспомните, что логическим присваиванием для X называется присваивание значения 0 или 1 каждой переменной х_i; другими словами, каждой переменной должно быть присвоено булево значение и ни одна переменная не должна остаться неопределенной. Логическое присваивание v называется согласованным с неполным присваиванием ρ, если каждая логическая переменна, определенная в ρ, имеет одинаковые значения в ρ и v. (Другими словами, если ρ(х_i) ≠ ?, то ρ(х_i) = v(x_i).) Наконец, мы говорим, что неполное присваивание ρ форсирует набор условий С₁, ..., C_m, если для каждого логического присваивания v, согласованного с р, v выполняет C₁, ..., C_m. (Также р будет называться форсирующим неполным присваиванием.)

А теперь вопрос, следующий из этих определений. Имеется набор булевых переменных X = {х₁, х₂, ..., x_n}, параметр b < n, и набор условий C₁, ..., C_m по переменным, в котором каждое условие представляет собой дизъюнкцию трех разных литералов. Требуется решить, существует ли для X форсирующее неполное присваивание ρ, в котором определено не более bпеременных. Предложите алгоритм, который решает задачу с временем вида O(f(b) ∙ p(n, m)), где p(∙) — полиномиальная функция, а f(∙) — произвольная функция, зависящая только от b, но не от n или m.

Решение

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

(10.22) Частичное присваивание ρ форсирует все условия в том, и только в том случае, если для каждого условия C_i по крайней мере одна из переменных в C_i определяется р так, что это выполняет C_i.

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

И наоборот, предположим, что существует такое условие C_i, что ρ не определяет никакие переменные в C_i способом, выполняющим C_i. Мы хотим показать, что ρ не является форсирующим, а для этого в соответствии с определением требуется представить присваивание, при котором выполняются не все условия. Рассмотрим следующее логическое присваивание v: v соответствует ρ по всем определенным переменным; присваивает произвольное логическое значение каждой неопределенной переменной, не входящей в C_i; и присваивает каждой неопределенной переменной в C_i значение, с которым условие не выполняется. Так как v присваивает каждой переменной в C_i значение, с которым оно не выполняется, следовательно, не является выполняющим присваиванием. Но v согласуется с ρ, а из этого следует, что оно не является форсирующим неполным присваиванием. ■

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

Попробуем действовать аналогично тому, как мы действовали при поиске малого вершинного покрытия. Выберем произвольное условие C_j, содержащее литералы х_i, x_j и х_k (возможно, с инвертированием). Из (10.22) известно, что любое форсирующее присваивание ρ должно присвоить одной из этих трех переменных значение, входящее в C_i, поэтому мы можем опробовать все три возможности. Допустим, мы задали переменную x_i так, как она входит в C_i; тогда из экземпляра можно исключить все условия (включая C'), выполняемые этим присваиванием х_i, и попытаться выполнить оставшиеся. Назовем это уменьшенное множество условий экземпляром, сокращенным по присваиванию х_i. То же самое можно сделать для х_j и х_k. Так как присваивание ρ должно определять одну из этих переменных в том состоянии, в каком она входит в C', а затем выполнять все остальное, нам удалось обосновать следующую аналогию с (10.3). (Чтобы упростить изложение, мы будем называть размером частичного присваивания количество определяемых им переменных.)

(10.23) Форсирующее присваивание с размером не более b существует в том, и только в том случае, если существует форсирующее присваивание с размером не более b - 1 для минимум одного из экземпляров, сокращенных по присваиванию х_i, х_j или х_k.

Итак, мы получаем следующий алгоритм. Его работа зависит от граничных случаев: отсутствия условий (тогда по определению выполнение считается успешным) и наличия условий с b = 0 (тогда следует объявление о неудаче).

Чтобы найти границу времени выполнения, мы рассматриваем дерево возможностей, по которому проводится поиск (как и в случае с алгоритмом нахождения вершинного покрытия). Каждый рекурсивный вызов порождает три дочерних узла в этом дереве, и это происходит на глубину до b. Таким образом, дерево содержит не более 1 + 3 + 3² + ... + 3^b ≤ 3^b+1 узлов, и в каждом узле для получения сокращенных экземпляров затраты времени не превышают O(m + n). Следовательно, общее время выполнения составляет O(3^b(m + n)).

Упражнения

1. В упражнении 5 главы 8 утверждалось, что задача множества представителей является NР-полной. Чтобы вспомнить определения, возьмем множество A = {a₁, ..., a_n} и набор B₁, B₂, ..., B_mподмножеств A. Множество H ⊆ A называется множеством представителей для набора B₁, B₂, ..., B_m, если H содержит по крайней мере один элемент из каждого B_i, то есть если результат H ∩ B_iне пуст для каждого i. (Иначе говоря, H содержит “представителя” из каждого множества B_i.)

Теперь предположим, что для имеющегося экземпляра задачи нужно определить, существует ли множество представителей с размером не более k. Кроме того, предположим, что каждое множество B_i содержит не более с элементов для константы с. Предложите алгоритм, который решает задачу с временем выполнения вида O(f(с, k) ∙ p(n, m)), где p(∙) — полиномиальная функция, а f(∙) — произвольная функция, зависящая только от с и k, но не от n или m.

Сложность задачи 3-SAT обусловлена тем фактом, что существуют 2ⁿ возможных присваиваний входным переменным х₁, х₂, ..., x_n при отсутствии очевидного способа поиска в этом пространстве за полиномиальное время. Впрочем, это интуитивное представление может создать неверное впечатление, что самые быстрые алгоритмы 3-SAT требуют времени 2ⁿ. Когда вы слышите об этом впервые, это кажется противоестественным, однако для 3-SAT существуют алгоритмы, работающие значительно быстрее 2ⁿ в худшем случае; другими словами, они определяют, существует ли выполняющее присваивание за меньшее время, чем необходимо для перебора всех возможных значений переменных. Здесь мы создадим один такой алгоритм, решающий экземпляры 3-SAT за время O(р(n) ∙ (√3)ⁿ) для некоторой полиномиальной функции р(n). Обратите внимание: основной составляющей в этом времени выполнения является (√3)ⁿ, то есть 1,74ⁿ.

(a) Для логического присваивания Ф с переменными x₁, x₂, ..., x_n запись Ф(х_i) обозначает значение, присвоенное Ф переменной х_i (0 или 1). Для двух логических присваиваний Ф и Ф' расстояние между Ф and Ф' определяется как количество переменных х_i, которым присваиваются разные значения; это расстояние обозначается d(Ф, Ф'). Другими словами, d(Ф, Ф') = |{i : Ф(х_i) ≠ Ф'(х_i)}|. Основным структурным элементом этого алгоритма будет способность отвечать на вопросы следующего типа: для заданного логического присваивания Ф и расстояния d требуется определить, существует ли такое выполняющее присваивание Ф', что расстояние от Ф до Ф' не превышает d.

Рассмотрим следующий алгоритм Ехрlоrе(Ф, d), который пытается ответить на этот вопрос:

Докажите, что Ехрlоrе(Ф, d) возвращает “да” в том, и только в том случае, если существует выполняющее присваивание Ф', для которого расстояние от Ф до Ф' не превышает d. Также приведите анализ времени выполнения Ехрlоrе (Ф, d) как функции от n и d.

(b) Очевидно, расстояние между любыми двумя присваиваниями Ф и Ф' не превышает n, так что один из способов решения заданного экземпляра 3-SAT заключается в выборе произвольного начального присваивания Ф и выполнении Ехрlоrе (Ф, n). Однако это не даст нужного нам времени выполнения.

Вместо этого мы сделаем несколько вызовов Explore из разных начальных точек Ф и каждый раз будем проводить поиск на более ограниченное расстояние. Опишите, как это сделать для того, чтобы экземпляр 3-SAT решался за время O(р(n) ∙ (√3)ⁿ).

2. Допустим, имеется направленный граф G = (V, E) с V = {v₁, v₂, ..., v_n} и нужно решить, существует ли в G гамильтонов путь от v₁ к v_n. (То есть существует ли в G путь, проходящий от v₁ к v_n через все остальные вершины ровно по одному разу?)

Так как задача о гамильтоновом пути является NР-полной, ожидать для нее решения с полиномиальным временем не приходится. Однако это не означает, что все алгоритмы с неполиномиальным временем одинаково “плохи”. Например, простейшее решение методом “грубой силы” выглядит так: для каждой перестановки вершин проверить, образует ли она гамильтонов путь от v₁ к v_n. Это займет время, приблизительно пропорциональное n!, что составляет около 3 х 10¹⁷ для n = 20.

Покажите, что задача о гамильтоновом пути может быть решена за время O(2ⁿ ∙ p(n)), где p(n) — полиномиальная функция от n. Для умеренных значений n этот алгоритм работает намного эффективнее; например, значение 2ⁿ для n = 20 всего лишь около миллиона.

3. Граф G = (V, E) называется триангулированным циклическим графом, если он состоит из вершин и ребер триангулированного выпуклого n-угольника на плоскости, другими словами, если он может быть нарисован на плоскости следующим образом.

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

Рис. 10.12. Триангулированный циклический граф: ребра образуют границу выпуклого многоугольника и отрезки, разделяющие внутреннюю область на треугольники

Докажите, что для каждого триангулированного циклического графа существует древовидная декомпозиция с шириной не более 2. Опишите эффективный алгоритм построения такой декомпозиции.

4. Задача о доминирующем множестве с минимальной стоимостью определяется ненаправленным графом G = (V, E) и стоимостями c(v) для узлов v ∈ V. Подмножество S ⊂ V называется доминирующим множеством, если все узлы u ∈ V – S соединяются ребром (u, v) с узлом v из S. (Обратите внимание на отличие между доминирующими множествами и вершинными покрытиями: в доминирующем множестве у ребра (u, v) узлы u и v могут не входить в множество S при условии, что у u и v имеются соседи в S.)

(a) Предложите алгоритм с полиномиальным временем для задачи о доминирующем множестве в частном случае, когда G является деревом.

(b) Предложите алгоритм с полиномиальным временем для задачи о доминирующем множестве в частном случае, когда G имеет древовидную ширину 2 и также имеется древовидная декомпозиция G с шириной 2.

5. Задача о путях, не пересекающихся по ребрам, определяется ненаправленным графом G и k парами узлов (s_i, t_i) для i = 1, ..., k. Требуется решить, существуют ли непересекающиеся по ребрам пути P_i, для которых путь P_i соединяет s_i с t_i. Предложите алгоритм с полиномиальным временем для задачи о путях, не пересекающихся по ребрам, для частного случая: граф G имеет древовидную ширину 2, и также имеется древовидная декомпозиция T графа G с шириной 2.

6. Хроматическим числом графа G называется минимальное значение k, при котором граф имеет k-раскраску. Как было показано в главе 8, принятие решения о том, имеет ли заданный входной граф хроматическое число ≤ k, является NP-полной задачей.

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

(b) Для заданного ненаправленного n-узлового графа G = (V, E) с древовидной шириной не более w покажите, как вычислить хроматическое число G за время O(f(w) ∙ p(n)), где p(∙) — полиномиальная функция, но f(∙) может быть произвольной функцией.

7. Рассмотрим класс экземпляров 3-SAT, в котором каждая из n переменных встречается (считая, как простые, так и инвертированные вхождения) ровно в трех условиях. Покажите, что любой такой экземпляр 3-SAT выполним и что выполняющее присваивание может быть найдено за полиномиальное время.

8. Предложите алгоритм с полиномиальным временем для следующей задачи. Имеется бинарное дерево T = (V, E) с нечетным числом узлов и неотрицательным весом каждого узла. Требуется найти разбиение узлов V на два множества равного размера с максимально возможным весом разреза между двумя множествами (то есть общим весом ребер, концы которых принадлежат разным подмножествам). Обратите внимание: ограничение на то, что граф является деревом, в этой задаче критично, а предположение о том, что дерево является бинарным, — нет. Для обобщенных графов задача является NP-сложной.

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

Самая первая тема этой главы (о том, как избежать времени выполнения O(kn^k+1) для задачи о вершинном покрытии) является примером общей темы параметризованной сложности; для задач с двумя такими “параметрами размера” n и k время выполнения в форме O(f(k) ∙ p(n)), где p(∙) — полиномиальная функция, обычно предпочтительнее времени выполнения в форме O(nk). По этой теме была проведена значительная работа, включая разработку методологии выявления NP-полных задач, которые, скорее всего, не допускают такого улучшения времени выполнения. Эта область описана в книге Дауни и Феллоуза (Downey, Fellows, 1999).

NP-полнота задачи раскраски множества дуг была доказана Гэри, Джонсоном, Миллером и Пападимитриу (Garey, Johnson, Miller, Papadimitriou, 1980). Они также описали, как алгоритм, представленный в этой главе, напрямую вытекает из конструкции, предложенной Такером (Tucker, 1975). Задачи о раскраске интервалов и дуг принадлежат следующему классу задач: взять набор геометрических объектов (таких, как интервалы или дуги), определить граф соединением пар пересекающихся объектов и проанализировать задачу раскраски полученного графа. В книге о раскраске графов Дженсена и Тофта (Jensen, Toft, 1995) приведены описания многих других задач этого типа.

Важность декомпозиций и древовидной ширины вышла на передний план в основном благодаря работе Робертсона и Сеймура (Robertson, Seymour, 1990). Алгоритм построения декомпозиции, описанный в разделе 10.5, был предложен в работе Дистела и др. (Diestel et. al., 1999). Дальнейшее обсуждение древовидной ширины и ее роли в алгоритмах и теории графов приведено в обзоре Рида (Reed, 1997) и книге Дистела (Diestel, 2000). Древовидная ширина также играет важную роль в алгоритмах вероятностных моделей машинного обучения, основанных на логическом выводе Джордан (Jordan, 1998).

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

Упражнение 2 основано на результатах Уве Шонинга; упражнение 8 основано на задаче, о которой мы узнали от Амита Кумара.

---

¹ Под “NР-сложностью” мы понимаем задачу “по крайней мере не проще NР-полной задачи”. Задачи оптимизации обычно не называют NР-полными, потому что формально этот термин относится только к задачам принятия решений.