Minimalny True Monotone 3SAT

Interesuje mnie odmiana SAT, w której wzór CNF jest monotoniczny (żadnych zmiennych nie neguje się). Taka formuła jest oczywiście zadowalająca.

Ale powiedzmy, że liczba prawdziwych zmiennych jest miarą tego, jak dobre jest nasze rozwiązanie. Mamy więc następujący problem:

MINIMALNY PRAWDZIWY MONOTON 3SAT

INSTANCJA: Zestaw U zmiennych, zbiór C rozłącznych klauzul 3 literałów, gdzie literał jest zmienną (nie negowaną).
ROZWIĄZANIE: Przypisanie prawdy dla U, które spełnia C.
POMIAR: Liczba prawdziwych zmiennych.

Czy ktoś mógłby mi przekazać kilka pomocnych uwag na temat tego problemu?

$3$$H$$V$$3$$U\subseteq V$$H$

$2-\epsilon$$\epsilon>0$

Irit Dinur, Venkatesan Guruswami, Subhash Khot i Oded Regev. New Multilayered PCP and Hardness of Hypergraph Vertex Cover , SIAM Journal on Computing, 34 (5): 1129–1146, 2005.

$W[1]$

$q$

$X$$q$

$k$

$k$