Bedingungen für die Rückverfolgbarkeit von 3SAT-Satisfiability

12

Ich frage mich insbesondere, ob es eine interessante Bedingung für den Prozentsatz der Aufgaben gibt, die eine 3SAT-Formel erfüllen, um sicherzustellen, dass solche Probleme behoben werden können.

Nehmen wir zum Beispiel die Klasse der 3SAT-Probleme an, dass der möglichen Zuordnungen die Boolesche Formel erfüllt; können wir effizient eine zufriedenstellende Aufgabe finden? Für das, was ist das resultierende Problem in P?ϵ(n)2n2nϵ

Anmerkung bearbeiten: Ersetzen Sie durch , um Verwirrung zu beseitigen.ϵϵ(n)

Rafi Witten
quelle
4
Eine einfache Beobachtung: Wenn höchstens invers polynomiell klein ist, ergibt eine gleichmäßige Abtastung von eine Lösung in der erwarteten Polynomzeit. Wenn also zwischen 1 und 1 / poly (n) liegt, ist dieses Problem einfach (in ZPP). 1 / ϵ ϵϵ1/ϵϵ
Robin Kothari
1
Wenn 1 / eps quasipolynomial ist, haben Sie einen randomisierten Quasipoly-Zeit-Algorithmus, was selbst überraschend wäre
Suresh Venkat

Antworten:

12

Ja. Wenn eine Konstante (oder 1 / polylog ( n ) ) ist und Ihnen versprochen wird, dass mindestens ϵ 2 n aller möglichen Zuweisungen die eingegebenen 3CNFs erfüllen, finden Sie eine solche Zuweisung in deterministischen Polynomen. Zeit.0<ϵ<11/Polylog(n)ϵ2n

Der Algorithmus ist nicht schwierig:

Claim: Unter dem Versprechen angegeben, muss eine konstante Größe Satz existieren von Variablen , die trifft alle Klauseln im 3CNF, in dem Sinne , dass alle 3-Klausel eine Variable aus enthalten S .SS

Anspruchsnachweis (Skizze): Andernfalls muss eine ausreichend große Familie von 3-Klauseln aus dem 3CNF existieren, in der jede Variable nur einmal vorkommt. Aber diese Familie, wenn sie ausreichend groß ist , hat bereits weniger als Anteil der Zuweisungen zu erfüllen. QEDϵ

Somit können Sie alle möglichen (konstanten) Zuordnungen zu . Bei jeder festen Zuordnung zu S wird der 3CNF zu einem 2CNF, wenn angenommen wird, dass S den ursprünglichen 3CNF trifft. Jetzt können Sie den bekannten polyzeitdeterministischen Algorithmus verwenden, um eine zufriedenstellende Zuordnung für 2CNF-Formeln zu finden. Insgesamt erhalten Sie eine Polynomzeitobergrenze.SSS

Der Algorithmus für 2SAT ist meiner Meinung nach schon in S. Cooks berühmtem Papier von 1971.

Der Algorithmus für 3CNFs stammt von: L. Trevisan Eine Anmerkung zur deterministischen Näherungszählung für k-DNF in Proc. von APPROX-RANDOM, Springer-Verlag, Seite 417-426, 2004

Die Originalarbeit, die das Ergebnis für 3CNF zeigt, lautet: E. Hirsch, Ein schneller deterministischer Algorithmus für Formeln mit vielen zufriedenstellenden Aufgaben , Journal of the IGPL, 6 (1): 59-71, 1998

Iddo Tzameret
quelle
Danke für die Antwort. Eigentlich interessierte ich mich für nicht konstante aber es ist interessant, die Existenz eines deterministischen Algorithmus zu lernen. Ich habe die Frage bearbeitet, um sie klarer zu machen. ϵ
Rafi Witten
1
@Rafi, ich denke, der gleiche Algorithmus funktioniert für nicht konstante . ϵ=1/polylog(n)
Iddo Tzameret
Wie konstruierst du S?
Radu GRIGore
1
@Radu, ich denke, Sie können das gierig tun: Wählen Sie eine beliebige erste Klausel . Wählen Sie dann eine andere Klausel C 2, deren Variablen von C 1 getrennt sind . Machen Sie so weiter, bis Sie keine Klausel mit disjunkten Variablen zu den Klauseln finden, die Sie bereits ausgewählt haben. Die Variablen in den von Ihnen ausgewählten Klauseln sind also die Treffermenge. C1C2C1
Iddo Tzameret