Параметризованная задача k-FLIP SAT определяется как:
Вход: формула 3-CNF с переменные и присвоение правды
Параметр:
Вопрос: можем ли мы преобразовать задание в удовлетворяющее назначение за перевернуть значение истины самое большее переменные?
Проблема явно в FPT ( Stefan Szeider: Параметризованная сложность локального поиска k-Flip для SAT и MAX SAT. Дискретная оптимизация 8 (1): 139-145 (2011) )
Допускает ли оно полиномиальное ядро? (при разумных допущениях сложности)
Недавние методы кросс-композиции (см. Ханс Л. Бодлаендер, Барт М.П. Янсен, Стефан Крач, «Нижние границы кернелизации с помощью кросс-композиции» ) кажутся бесполезными для этой проблемы. И они также кажутся бесполезными для подобных проблем, которые спрашивают, может ли данное решение NP-трудной проблемы быть найдено из данного экземпляра локальным поиском (ограничивая поиск соседями данного экземпляра, по некоторой естественной мере расстояния).
источник
Ответы:
Проблема не имеет ядра полинома, если NP не находится в coNP / poly. Техника кросс-композиции из нашей статьи применяется нетривиальным образом.
Позвольте мне показать, как классическая задача покрытия вершин ИЛИ пересекается с задачей k-FLIP-SAT; по результатам цитируемой статьи этого достаточно. Конкретно, мы строим алгоритм за полиномиальное время, вход которого представляет собой последовательность экземпляров Vertex Cover(г1, к ) , (г2, к ) , … , (гT, к ) что все имеют одинаковую ценность К и у всех точно N Вершины. Вывод является экземпляромК -FLIP SAT со значением параметра O ( k + logт ) который достаточно мал для перекрестного состава, так что К -FLIP SAT экземпляр имеет ответ да, если один из входных графов имеет размер вершины К , Дублируя один вход (который не меняет значение ИЛИ), мы можем гарантировать, что количество входовT это сила двух.
Композиция происходит следующим образом. Пронумеруйте вершины в графе каждого входного графагя в виде vi,1,vi,2,…,vi,n , Создайте соответствующую переменную в экземпляре FLIP-SAT для каждой вершины каждого входного графа. Дополнительно сделайте переменную селектораui для каждого входного номера экземпляра i∈[t] , Для каждого входного графикаGi Мы добавим несколько пунктов в формулу. Для каждого края{vi,x,vя,y} графика гя добавить пункт (vя , х∨vя , у∨ ¬Uя) в формулу, которая будет кодировать "либо одна из конечных точек этого ребра установлена в true, либо экземпляр я не активен ". В начальном присваивании все вершинные переменные установлены в false и все переменные селектора Uя устанавливаются в ложь, так что все эти пункты выполняются. Чтобы встроить OR-поведение в композицию, мы расширим формулу, чтобы убедиться, что удовлетворяющее присваивание устанавливает хотя бы один селектор в true, а затем должно также сформировать покрытие вершин выбранного графа.
Чтобы убедиться, что мы можем сделать этот выбор, сохраняя маленькое расстояние переворачивания по сравнению с количеством входовT мы используем структуру полного бинарного дерева с T листья, которые имеют высоту журналT , Номер листьев от1 в T и связать я лист с переменной Uя это контролирует, если вход я активен или нет. Создайте новую переменную для каждого внутреннего узла двоичного дерева. Для каждого внутреннего узла пусть его соответствующая переменная будетИкс и переменные его двух детей будут Y а также Z , Добавить пункт( ¬ x ∨ у∨ з) к формуле, которая отражает значение ( х → ( у∨ з) ) , обеспечивая это Икс может быть правдой, только если один из его детей правдив. Чтобы завершить формулу, добавьте одноэлементное предложение о том, что переменная корневого узла двоичного дерева должна быть истинной. В начальном назначении истинности значения всех переменных для внутренних узлов устанавливаются в false, что удовлетворяет всем пунктам формулы, за исключением предложения singleton, требующего, чтобы корневой узел дерева имел свою переменную true.
Это завершает описание формулы и присвоения правды. Установите параметрК' задачи ПЕРЕКЛЮЧЕНИЕ ДИСТАНЦИИ, чтобы быть равным ( к + логт + 1 ) , который соответствующим образом ограничен для кросс-композиции. Осталось показать, что мы можем перевернутьК' переменные, чтобы сделать формулу истинной, если некоторый входной граф гя имеет размер вершины К ,
В обратном направлении предположим, чтогя имеет размер-К покрытие вершины. УстановитьК переменные, соответствующие К вершины в покрытии к истине, переворачивая их. Установите переменную селектораUя в true, чтобы закодировать этот вход я активируется и переворачивает переменные журналT внутренние двоичные узлы дерева на пути листа я в корень к истине. Нетрудно убедиться, что это удовлетворительное назначение: все значения в двоичном дереве удовлетворены, значение корневого узла установлено в true, пункты, которые проверяют ребрагя' за я'≠ я оставайтесь довольны, потому что Uя' остается ложным, в то время как предложения для графа гя удовлетворены, потому что для каждого ребра мы устанавливаем по крайней мере одну конечную точку в true.
Для прямого направления, предположим, что формула может быть удовлетворена, перевернув самое большеек + логт + 1 переменные. Затем мы должны перевернуть переменную корневого узла в true. Последствия в двоичном дереве приводят к тому, что, по крайней мере, одна переменная селектора листа имеет значение true, скажем,Uя , Чтобы удовлетворить последствия, закодированные в двоичном дереве, все внутренние узлы на пути отUя в корне были установлены в true, с учетом 1 + журналT переворачивается. посколькуUя установлен в true, пункты сделаны для графа гя не удовлетворены буквально ¬Uя , поэтому они удовлетворены, потому что одна из конечных точек каждого края гя установлен в true. Так как по крайней мере1 + журналT переменные двоичного дерева были перевернуты, самое большее К переменные вершины перевернуты в true в этом решении. Это кодирует покрытие вершины размераК в гя и доказывает, что один из входных данных является экземпляром YES. Это завершает доказательство.
источник