Minimalny True Monotone 3SAT

11

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?

krumpelstiltskin
źródło

Odpowiedzi:

21

3HV3UVH

2ϵϵ>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.

Jan Johannsen
źródło
Innym słowem kluczowym byłoby „Zestaw 3 uderzeń”. Nie mam teraz dostępu do następującego artykułu, ale tytuł wydaje się istotny: scholar.google.co.uk/…
Radu GRIGore
Próg zbliżenia wynosi w rzeczywistości . 3ϵ
Mahdi Cheraghchi,
1
@MCH: Odniesienie?
Tsuyoshi Ito
1
Nie, jego : dla k- jednorodnego pokrycia hiperrafraftu wykazują twardość aproksymacji do wewnątrz ( k - 1 - ϵ ) . 2ϵk(k1ϵ)
Jan Johannsen,
1
Ups ... @MCH: Jestem zainteresowany, aby zobaczyć wynik, jak również. oznaczałoby to, że trywialny algorytm aproksymacyjny jest najlepszy, na jaki możemy liczyć. 3ϵ
krumpelstiltskin
7

W[1]

q

Xq

k

k

Anthony Labarre
źródło