Minimum True Monoton 3SAT

Saya tertarik pada variasi SAT di mana rumus CNF adalah monoton (tidak ada variabel yang dinegasikan). Formula seperti itu jelas memuaskan.

Tetapi katakanlah jumlah variabel benar adalah ukuran seberapa baik solusi kami. Jadi kami memiliki masalah berikut:

MINIMUM TRUE MONOTONE 3SAT

INSTAN: Tetapkan U variabel, koleksi C dari klausa disjungtif 3 literal, di mana literal adalah variabel (tidak dinegasikan).
SOLUSI: Tugas kebenaran untuk U yang memuaskan C.
UKURAN: Jumlah variabel yang benar.

Bisakah seseorang memberi saya komentar yang bermanfaat tentang masalah ini?

Masalah ini adalah sama dengan masalah Vertex Cover untuk hypergraphs -uniform: diberikan koleksi himpunan bagian dari ukuran masing-masing, menemukan minimal bagian yang berpotongan setiap set di .$3$$H$$V$$3$$U\subseteq V$$H$

Oleh karena itu NP-hard, tetapi traktat parameter tetap. Juga sulit NP untuk mendekati dalam faktor untuk setiap . Ini ditunjukkan dalam makalah berikut:$2-\epsilon$$\epsilon>0$

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

Saya akan mulai dengan melihat makalah yang mengutip makalah Downey dan Fellows , di mana mereka mempertimbangkan masalah berikut dan membuktikan kelengkapan .$W[1]$

TERTIMBANG -CNF SAT$q$

Instance: Formula CNF (yaitu, rumus dalam Conjunctive Normal Form) di mana setiap klausa berisi variabel .$X$$q$

Parameter: Bilangan bulat positif .$k$

Pertanyaan: Apakah X memiliki penugasan bobot yang memuaskan , di mana bobot penugasan adalah jumlah variabel yang disetel ke "benar"?$k$