Bekannteste asymptotische PCP-Größen / 3-SAT

Was sind die bekanntesten asymptotischen Obergrenzen für die Größe probabilistisch überprüfbarer Beweise? Idealerweise suche ich nach einer zeitgemäßen Umfrage zu dieser umfassenden Frage, aber wenn es keine gibt, bin ich besonders an der Unannäherbarkeit von 3-SAT interessiert.

Sei 7/8 + ε-3-SAT 3-SAT mit dem Versprechen, dass die Instanz erfüllbar ist, wenn 7/8 + ε Bruchteil der Klauseln erfüllt werden kann. Was sind die bekanntesten Reduktionen von 3-SAT mit Klauseln auf 7/8 + ε-3-SAT? Gibt es zum Beispiel eine Reduzierung mit -Klauseln? ( -Klauseln sind ein offenes Problem.) Eine Verringerung der einheitlichen quasilinearen Größe NC? Was ist die Abhängigkeit von , auch wenn ? Gibt es eine bekannte lineare Größenreduktion (abhängig von ) von (1-ε) -3-SAT auf 7/8 + ε-3-SAT, und wenn nicht, haben wir bessere Grenzen für (1-ε) -3 -SAT? Auch eine teilweise Antwort wäre interessant. $n$ $O(n \log n)$ $O(n)$ $ε$ $ε→0$ $ε$

Auch wenn dies die Frage vielleicht zu weit gefasst machen würde, sollte ich erwähnen, dass ein weiteres wichtiges Thema hier die konstanten Faktoren sind, die aufgrund von Techniken wie dem langen Code üblicherweise nicht realisierbar sind.

cc.complexity-theory reference-request np-hardness pcp Dmytro Taranovsky
quelle

Antworten:

Der Stand der Technik für PCPs, die eine Reduktion auf 3-SAT (auch für subkonstante ) ergeben, sind die von Dana Moshkovitz und Ran Raz , die habe die Länge . Ich weiß jedoch nicht, ob jemand versucht hat, die genaue Abhängigkeit der Länge von oder die Rechenkomplexität der Reduktion zu berechnen . Ihr technisches Hauptergebnis wurde später von Irit Dinur und Prahladh Harsha vereinfacht . $(\frac{7}{8}+\varepsilon)$ $\varepsilon$ $n^{1 + o(1)}$ $\varepsilon$

Wenn Sie an kurzen PCPs mit einer konstanten Anzahl von Abfragen interessiert sind, die nicht unbedingt eine optimale Verringerung der Approximationshärte ergeben (auch als "PCPs mit hohem Fehler" bezeichnet), sind PCPs der Länge das Stand der Technik aufgrund von Eli Ben-Sasson und Madhu Sudan und seiner Verbesserung durch Dinur . Auch hier weiß ich nicht, ob jemand die genaue Komplexität der Berechnung der Reduktion ist. $n\cdot \mathrm{poly}\log n$

Oder Meir
quelle

Vielen Dank; Beide Teile waren hilfreich. Ich stelle fest, dass quasilineares PCP mit O (1) -Abfragen und konstantem Fehler ein offenes Problem bleibt.

Dmytro Taranovsky

Nein, das ergibt sich tatsächlich aus der Arbeit von Ben-Sasson und Sudan. Es ist ein offenes Problem, solche PCPs mit subkonstanten Fehlern zu erhalten.

Oder Meir

Ich habe noch etwas nachgesehen und Dinur 2007 erweitert das im zweiten Absatz zitierte Papier, um . Wenn ich das richtig verstehe, impliziert dies eine Reduzierung von 3-SAT auf eine quasilineare Größe von 3-SAT, aber das Ergebnis, das Sie im ersten Absatz zitiert haben, ist nicht redundant, da es uns 7/8 und mehr ergibt .

S A T \in P C P_{\frac{1}{2}, 1} [\log_{2} n + O (\log \log n), O (1)]

$SAT ∈ PCP_{\frac{1}{2},1}[\log_2 n + O(\log \log n), O(1)]$

1 - ε

$1-ε$

7 / 8 + ε

$7/8+ε$

Dmytro Taranovsky

Ja das ist richtig. Ich habe vergessen, Dinurs Ergebnis zu erwähnen, ich werde es der Antwort hinzufügen.

Oder Meir