Minimum True Monotone 3SAT

Ich interessiere mich für eine SAT-Variante, bei der die CNF-Formel monoton ist (keine Variablen werden negiert). Eine solche Formel ist offensichtlich erfüllbar.

Angenommen, die Anzahl der wahren Variablen ist ein Maß dafür, wie gut unsere Lösung ist. Wir haben also folgendes Problem:

MINIMUM TRUE MONOTONE 3SAT

INSTANZ: Setze U von Variablen, Sammlung C von Disjunktivsätzen von 3 Literalen, wobei ein Literal eine Variable ist (nicht negiert).
LÖSUNG: Eine Wahrheitszuweisung für U, die C erfüllt.
MASSNAHME: Die Anzahl der Variablen, die wahr sind.

Könnte mir jemand hilfreiche Bemerkungen zu diesem Problem geben?

Dieses Problem ist dasselbe wie das Vertex-Cover-Problem für einheitliche Hypergraphen: Wenn eine Sammlung H von Teilmengen von V der Größe 3 vorliegt, finden Sie eine minimale Teilmenge U ⊆ V , die jede Menge in H schneidet .$3$$H$$V$$3$$U\subseteq V$$H$

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

Irit Dinur, Venkatesan Guruswami, Subhash Khot und Oded Regev. Ein neues mehrschichtiges PCP und die Härte der Hypergraph Vertex Cover , SIAM Journal on Computing, 34 (5): 1129–1146, 2005.

$W[1]$

$q$

$X$$q$

$k$

$k$