Mínimo verdadero monótono 3SAT

Estoy interesado en una variación SAT donde la fórmula CNF es monótona (no se niegan variables). Tal fórmula es obviamente satisfactoria.

Pero digamos que el número de variables verdaderas es una medida de cuán buena es nuestra solución. Entonces tenemos el siguiente problema:

MÍNIMO VERDADERO MONOTONE 3SAT

INSTANCIA: Conjunto U de variables, colección C de cláusulas disyuntivas de 3 literales, donde un literal es una variable (no negada).
SOLUCIÓN: Una asignación de verdad para U que satisface C.
MEDIDA: El número de variables que son verdaderas.

¿Podría alguien darme algunos comentarios útiles sobre este problema?

Este problema es el mismo que el problema Vertex Cubierta para hypergraphs Uniform: Dada una colección de subconjuntos de de tamaño cada uno, encontrar un mínimo subconjunto que intersecta cada conjunto en .H V 3 U ⊆ V $3$$H$$V$$3$$U\subseteq V$$H$

Por lo tanto, es NP-hard, pero el parámetro fijo es manejable. También es NP-difícil aproximarse a un factor de por cada . Esto se mostró en el siguiente documento:ϵ > $2-\epsilon$$\epsilon>0$

Irit Dinur, Venkatesan Guruswami, Subhash Khot y Oded Regev. Un nuevo PCP multicapa y la dureza de la cubierta de vértices de hipergrafía , SIAM Journal on Computing, 34 (5): 1129-1146, 2005.

Comenzaría por echar un vistazo a los documentos que citan el papel de Downey y Fellows , en el que consideran el siguiente problema y prueban su integridad .$W[1]$

$q$

$X$$q$

$k$

$k$