Минимальный истинный монотон 3SAT

Меня интересует вариация SAT, где формула CNF является монотонной (никакие переменные не отменяются). Такая формула, очевидно, выполнима.

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

МИНИМАЛЬНЫЙ ИСТИННЫЙ МОНОТОН 3SAT

INSTANCE: набор U переменных, коллекция C дизъюнктивных предложений из 3 литералов, где литерал является переменной (не отрицается).
РЕШЕНИЕ: присваивание истинности для U, которое удовлетворяет C.
MEASURE: количество переменных, которые являются истинными.

Может ли кто-нибудь дать мне несколько полезных замечаний по этой проблеме?

Эта проблема является таким же , как проблема вершинной Обложки для -равномерных гиперграфов: дано коллекция подмножеств размера каждых, найти минимальное подмножество , который пересекает каждое множество в .$3$$H$$V$$3$$U\subseteq V$$H$

Поэтому он NP-жесткий, но с фиксированными параметрами. Это также NP-трудно приблизиться к в пределах фактора для каждой . Это было показано в следующей статье:$2-\epsilon$$\epsilon>0$

Ирит Динур, Венкатесан Гурусвами, Субхаш Хот и Одед Регев. Новый многослойный PCP и твердость покрытия вершины гиперграфа , SIAM Journal of Computing, 34 (5): 1129–1146, 2005.

Я бы начал с того, что взглянул на статьи со ссылкой на статью Дауни и Феллоуза , в которой они рассматривают следующую проблему и доказывают ее -полноту.$W[1]$

WEIGHTED -CNF СБ$q$

Экземпляр: формула CNF (т. Е. Формула в конъюнктивной нормальной форме), в которой каждое предложение содержит переменных.$X$$q$

Параметр: положительное целое число .$k$

Вопрос: Есть ли у X удовлетворительное присваивание веса , где вес присваивания - это число переменных, которые он устанавливает в «true»?$k$