Minimum True Monotone 3SAT

Je m'intéresse à une variation SAT où la formule CNF est monotone (aucune variable n'est niée). Une telle formule est évidemment satisfaisable.

Mais disons que le nombre de vraies variables est une mesure de la qualité de notre solution. Nous avons donc le problème suivant:

VÉRITABLE MONOTONE 3SAT MINIMUM

INSTANCE: Ensemble U de variables, collection C de clauses disjonctives de 3 littéraux, où un littéral est une variable (non niée).
SOLUTION: Une affectation de vérité pour U qui satisfait C.
MESURE: Le nombre de variables qui sont vraies.

Quelqu'un pourrait-il me faire quelques remarques utiles sur ce problème?

Ce problème est le même que le problème Vertex pour hypergraphes -uniform: donné une collection de sous - ensembles de de taille chacun, trouver un sous - ensemble minimal qui coupe chaque jeu en .$3$$H$$V$$3$$U\subseteq V$$H$

Il est donc NP-dur, mais paramètre paramétrable. Il est également difficile de se rapprocher de NP dans un facteur de pour chaque . Cela a été montré dans le document suivant:$2-\epsilon$$\epsilon>0$

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

Je commencerais par jeter un coup d'œil aux articles citant l'article de Downey et Fellows , dans lesquels ils examinent le problème suivant et prouvent sa .$W[1]$

PONDERE -CNF SAT$q$

Instance: une formule CNF (c'est-à-dire une formule sous forme normale conjonctive) dans laquelle chaque clause contient variables.$X$$q$

Paramètre: Un entier positif .$k$

Question: X a-t-il une affectation satisfaisante du poids , où le poids d'une affectation est le nombre de variables qu'il définit comme «vrai»?$k$