Finden Sie

9

Sei die Sprache aller CNF-Formeln , so dass mindestens $L_\epsilon$ $2$ $\varphi$ der-Klauseln können erfüllt sein. $(\frac{1}{2}+\epsilon)$ $\varphi$

Ich muss beweisen, dass es st gibt, das für jedes -hart ist . $\epsilon'$ $L_\epsilon$ $\mathsf{NP}$ $\epsilon<\epsilon'$

Wir wissen, dass ungefähr $\text{Max}2\text{Sat}$ Präzent der Klauseln aus einerReduzierung. Wie soll ich dieses Problem lösen? $\frac{55}{56}$ $\text{Max}3\text{Sat}$

complexity-theory satisfiability approximation Joni
quelle

8

$21/22$ $\leq \alpha$ $\geq (22/21) \alpha$ $\alpha \geq 1/2$ $p$ $1/2$ $a \land \lnot a$ $1/2 + p (\alpha - 1/2)$ $1/2 + p((22/21)\alpha - 1/2)$ $1/2$

Yuval Filmus
quelle

Funktioniert Ihre Methode, wenn ε eine beliebige (aber ausreichend kleine) reelle Zahl ist? Ich kann nicht herausfinden, wie ich die geeignete Anzahl von Klauseln für das Auffüllen auswählen soll, es sei denn, ich gehe von etwas über ε aus. (Beachten Sie, dass ε nicht Teil der Eingabe ist und es daher gut definiert ist, die reelle Zahl ε zu berücksichtigen.)

Tsuyoshi Ito

1 / 2 + p (α - 1 / 2)

$1/2+p(\alpha-1/2)$

1 / 2 + p ((22 / 21) α - 1 / 2)

$1/2+p((22/21)\alpha-1/2)$

α

$\alpha$

p

$p$

Aha, irgendwie dachte ich, dass diese Methode nicht funktioniert hat, als ich sie zuerst ausprobiert habe, aber jetzt sehe ich, wie sie funktioniert. Vielen Dank!

Tsuyoshi Ito

5

Wenn Sie wissen, dass ε eine rationale Zahl ist, brauchen Sie keine Unannäherbarkeit für Max-2-SAT, um Ihre Aussage zu beweisen. Ein typischer Beweis für die NP-Härte von Max-2-SAT (z. B. der im Lehrbuch Computational Complexity von Papadimitriou) belegt tatsächlich die NP-Vollständigkeit von L _1/5 . Um die NP-Härte zu beweisen L _ε für eine positive rationale Zahlen ε <1/5, können wir reduzieren L _1/5 bis L _ε wie folgt: Da eine 2CNF Formel φ (eine Instanz für L _1/5 ), lassen Sie m sein die Anzahl der darin enthaltenen Klauseln. Lass r unds sind positive ganze Zahlen, so dass (1 / 5− ε ) mr = 2 ε s gilt. Konstrukt dann eine 2CNF Formel (eine Instanz für L _ε ) durch Wiederholen φ für r - mal und Hinzufügen s Paare von widersprechenden Klauseln. Eine einfache Berechnung zeigt, dass dies tatsächlich eine Verringerung von L _1/5 auf L _{ε ist} .

Diese Reduktion funktioniert eindeutig nur, wenn ε rational ist, da sonst r und s nicht als ganze Zahlen genommen werden können. Der allgemeine Fall, in dem ε nicht unbedingt rational ist, scheint Unannäherbarkeit zu erfordern, wie Yuval Filmus in seiner Antwort schrieb.

Tsuyoshi Ito
quelle

Finden Sie

Antworten: