Задачи о разбиении - NP-полнота и вычислительная неразрешимость

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

Задача о трехмерном сочетании

Начнем с обсуждения задачи о трехмерном сочетании, которая может считаться усложненной версией задачи о двудольном паросочетании, которая разбиралась ранее. Задача о двудольном паросочетании может рассматриваться следующим образом: даны два множества X и Y, каждое из которых имеет размер n, и множество Р пар из X х Y. Вопрос: существует ли в Р такое множество из n пар, в котором каждый элемент в X U Y содержится ровно в одной паре? Связь с задачей двудольного паросочетания очевидна: множество Р таких пар просто соответствует ребрам двудольного графа.

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

Для заданных непересекающихся множеств X, Y и Z, каждое из которых имеет размер n, и заданного множества T ⊆ X х Y х Z упорядоченных триплетов существует ли в T такое множество из nтриплетов, что каждый элемент X U Y U Z содержится ровно в одном из этих триплетов?

Такой набор триплетов называется идеальным трехмерным сочетанием.

Интересный аспект задачи о трехмерном сочетании, кроме ее связи с двудольным паросочетанием, заключается в том, что она одновременно образует частные случаи как задачи покрытия множества, так и задачи упаковки множества: фактически мы ищем покрытие универсального множества X U Y U Z набором непересекающихся множеств. Конкретнее, задача о трехмерном сочетании является частным случаем задачи покрытия множества, поскольку мы ищем покрытие универсального множества U = X U Y U Z с использованием не более n множеств из заданного набора (триплетов). Аналогичным образом задача о трехмерном сочетании является частным случаем задачи упаковки множества, так как мы ищем n непересекающихся подмножеств универсального множества U = X U Y U Z.

Доказательство NР-полноты трехмерного сочетания

Приведенные выше рассуждения легко преобразуются в доказательства того, что Трехмерное сочетание ≤_р Покрытие множества и Трехмерное сочетание ≤_р Упаковка множества. Но это не поможет установить NР-полноту задачи о трехмерном сочетании, потому что эти сведения просто показывают, что задача о трехмерном сочетании может быть сведена к некоторым очень сложным задачам. Нам нужно провести доказательство в обратном направлении: что известная NР-полная задача может быть сведена к задаче о трехмерном сочетании.

(8.20) Задача о трехмерном сочетании является NР-полной.

Доказательство. Как и следовало ожидать, принадлежность задачи о трехмерном сочетании NР доказывается легко. Для заданного набора триплетов T ⊂ X х Y х Z сертификатом, подтверждающим решение, может быть набор триплетов T ⊆ T. За полиномиальное время можно убедиться в том, что каждый элемент в X U Y U Z принадлежит ровно одному из триплетов в T'.

Для сведения мы снова возвращаемся к задаче 3-SAT. Пожалуй, это выглядит более странно, чем в случае с гамильтоновым циклом, из-за тесной связи задачи о трехмерном сочетании с задачами упаковки множества и покрытия множества; но в действительности закодировать требования к разбиению в любой из этих задач очень трудно. Итак, рассмотрим произвольный экземпляр 3-SAT с n переменными х₁, ..., x_n и k условиями C₁, ..., C_k. Мы покажем, как решить его, если существует возможность обнаружения идеальных трехмерных сочетаний.

Общая стратегия такого сведения очень похожа (на очень высоком уровне) на метод, который использовался в сведении 3-SAT к гамильтоновому циклу. Сначала мы спроектируем регуляторы для кодирования независимых вариантов выбора, задействованных в логическом присваивании каждой переменной; затем будут добавлены регуляторы для кодирования ограничений, наложенных условиями. В этом построении все элементы экземпляра трехмерного сочетания будут изначально называться просто “элементами” без указания того, берутся ли они из X, Y или Z. В конце они естественным образом раскладываются на эти три множества.

Рассмотрим базовый регулятор, связанный с переменной х_i. Определим элементы A_i = {а_i1, a_i2, ..., a_i,2k}, образующие ядро регулятора; определим элементы B_i = {b_i1, ..., b_i,2k} на концах регулятора. Для всех j = 1, 2, ..., 2k определяется триплет t_ij = (a_ij, a_ij+1, b_ij) с интерпретацией сложения по модулю 2k. Три таких регулятора изображены на рис. 8.9. В регуляторе i триплет t_ijназывается четным, если j четно, или нечетным, если j нечетно. Аналогичным образом конец b_ij будет называться четным или нечетным.

Это будут единственные триплеты, содержащие элементы A_i, поэтому мы уже можем что-то сказать о том, как они должны покрываться в любом идеальном сочетании: необходимо использовать либо все четные триплеты в регуляторе i, либо все нечетные триплеты в гаджете i. На этой идее основан наш метод кодирования идеи о том, что х_i задается значение 0 или 1; выбор всех четных триплетов представляет назначение х_i = 0, а выбор всех нечетных триплетов представляет назначение х_i = 1.

Решение о четности/нечетности также может рассматриваться с другой точки зрения — в контексте концов регуляторов. Решив использовать четные триплеты, мы покрываем четные концы регуляторов и оставляем нечетные концы свободными; для нечетных триплетов покрываются четные концы регуляторов, а нечетные концы остаются свободными. Таким образом, решение о присваивании х можно рассматривать следующим образом: свободные нечетные концы соответствуют 0, тогда как свободные четные концы соответствуют 1. Пожалуй, такое представление упростит понимание оставшейся части построения.

Пока что выбор четности/нечетности может приниматься независимо для каждого из n регуляторов переменных. Теперь добавим элементы для моделирования условий и ограничения выбираемых вариантов присваивания. Как и в доказательстве (8.17), рассмотрим пример условия

На языке трехмерных сочетаний это означает: “Сочетание по центрам регуляторов должно оставить свободными четные концы первого регулятора; или оно должно оставить свободными нечетные концы второго регулятора; или оно должно оставить свободными нечетные концы третьего регулятора”. Итак, мы добавляем регулятор условия, который делает именно это. Он состоит из множества двух элементов ядра P₁ = {p₁, p'₁} и трех триплетов, их содержащих. Один триплет имеет форму (p₁, p'₁, b_1j) для четного конца b_1j; другой включает p₁, p'₁и нечетный конец b_2j'; и третий включает p₁, p'₁и четный конец b_3,j". Только эти три триплета покрывают P₁, поэтому мы знаем, что один из них должен использоваться; тем самым точно обеспечивается соблюдение условия.

В общем случае для условия C_j создается регулятор с двумя элементами ядра P_j = {р_j, p'_j}, а также определяются три триплета, содержащие P_j. Предположим, условие С_j содержит литерал t. Если t = х_i, мы определяем триплет (р_j, p'_j, b_i,2j); если то определяется триплет (р_j, p'_j, b_i,2j-1). Только регулятор условия j использует концы b_im c m = 2j или m = 2j - 1; таким образом, регуляторы условий никогда не “конкурируют” друг с другом за свободные концы.

Построение почти закончено, но осталась еще одна проблема. Допустим, множество условий имеет выполняющее присваивание. В этом случае для каждого регулятора переменной принимается соответствующий выбор четности/нечетности; для каждого регулятора условия остается как минимум один свободный конец, так что все элементы ядер регуляторов условий также получают покрытие. Проблема в том, что покрытие получили еще не все концы. Мы начали с n ∙ 2k = 2nk концов; триплеты {t_ij} обеспечили покрытие nk из них, а регуляторы условий — еще k. Остается обеспечить покрытие еще (n - 1)k концов.

Проблема решается очень простым приемом: в конструкцию добавляются (n - 1)k “регуляторов завершения”. Регулятор завершения i состоит из двух элементов ядра Q_i = {q_i, q'_i} и триплета (q_i, q_i, b) для каждого конца b в каждом регуляторе переменной. Это последняя часть построения.

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

И наоборот, предположим, что в построенном экземпляре существует идеальное трехмерное сочетание. Тогда, как упоминалось выше, в каждом регуляторе переменной сочетание выбирает либо все четные {t_ij}, либо все нечетные {t_ij}. В первом случае в экземпляре 3-SAT задаются х_i = 0, а во втором — х_i = 1. Теперь рассмотрим условие C_j; было ли оно выполнено? Так как два элемента ядра в P_j получили покрытие, по крайней мере один из трех регуляторов переменных, соответствующих литералам из C_j, сделал “правильный” выбор решения четности/нечетности, что привело к присваиванию, удовлетворяющему C_j.

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

К счастью, ответ на этот вопрос положителен. Мы можем определить X как множество всех a_ij c четными j, множество всех p_j и множество всех q_i. Y определяется как множество всех а_ij с нечетными j, множество всех p'_j и множество всех q'_j. Наконец, Z определяется как множество всех концов b_ij. Легко убедиться в том, что каждый триплет содержит по одному элементу из множеств X, Y и Z. ■

Рис. 8.9. Сведение задачи 3-SAT к задаче о трехмерном сочетании