Wie hat sich herausgestellt, dass die MA-Version von SETH falsch ist?

13

Nach diesem Aufsatz , der eine nichtdeterministische Erweiterung der Artikel Strong Exponential Time Hypothesis (SETH) diskutiert, heißt es: "[…] Williams hat kürzlich gezeigt, dass verwandte Hypothesen zur Merlin-Arthur-Komplexität von k-TAUT falsch sind." Dieses Papier zitiert jedoch nur eine persönliche Mitteilung.

Wie hat sich herausgestellt, dass die MA-Version von SETH falsch ist?

Ich vermute, dass es sich um eine Algebrierung der Formel handelt, habe aber keine weitere Idee.

Argentpepper
quelle
Könnten Sie das Dokument posten, wenn Sie eine Antwort erhalten?
13
Eine Zeitung kommt bald. Danke für Ihre Geduld.
Ryan Williams
3
Eigentlich werde ich sagen, dass das, was ich beweise, viel stärker ist als: "Es gibt ein -maliges Merlin-Arthur-Protokoll zur Widerlegung von k-TAUT", dh nicht erfüllbare k-CNF-Formeln. Sie können ungefähr 2 n / 2 Zeit bekommen, um einen UNSAT-Schaltkreis mit sublinearer Tiefe zu widerlegen, soweit ich das beurteilen kann. Aber wie gesagt, die Zeitung kommt bald. 1.9n2n/2
Ryan Williams
2
Möglicherweise dumme Frage, ist dieses Ergebnis (im Wesentlichen) auf die Idee zusteuernd: Die Vermutungen "NSETH" und "k-TAUT erfordert Schaltkreise mit exponentieller Größe" schließen sich gegenseitig aus? Oder verschlingt die PRG-Konstruktion leicht eine potenzielle Lücke zwischen der MA- und der NP-Komplexität von k-TAUT?
Joe Bebel
2
Keine dumme Frage! Kurze Antwort ist, dass ich es noch nicht weiß.
Ryan Williams

Antworten:

21

Sie finden einen Preprint unter diesem Link http://eccc.hpi-web.de/report/2016/002/

BEARBEITEN (1/24) Auf Anfrage finden Sie hier eine kurze Zusammenfassung, die dem Papier selbst entnommen ist, aber viele Dinge beschönigt. Angenommen Merlin kann Arthur beweisen , dass für eine -variable Rechenschaltung C , dessen Wert in allen Punkten in { 0 , 1 } k ist eine bestimmte Tabelle von 2 k Feldelemente, in der Zeit um ( s + 2 k ) d , Dabei ist s die Größe von C und d der Grad des von C berechneten PolynomskC{0,1}k2k(s+2k)dsCdC. (Wir nennen dies einen "kurzen, nicht interaktiven Beweis der Chargenbewertung" - die Bewertung von bei vielen Aufgaben.)C

Dann kann Merlin SAT für Arthur wie folgt lösen . Bei einem CNF F auf n Variablen und m Klauseln, Merlin und Arthur zuerst eine arithmetische Schaltung konstruieren C auf n / 2 Variablen vom Grad höchstens m n , Größe etwa m n 2 n / 2 , der eine Summe über alle Zuweisungen dauert die ersten n / 2 Variablen des CNF F (Addition einer 1 zur Summe, wenn F wahr ist, und 0#FnmCn/2mnmn2n/2n/2F1F0 wenn es falsch ist). Mit dem Chargenbewertungsprotokoll kann Merlin dann nachweisen, dass 2 n / 2 annimmtC2n/2 bestimmte Werte auf alle seine Boolesche Zuweisungen, in etwa 2 N / 2 p o l y ( n , m ) die Zeit. Fasst man all diese Werte, erhalten wir die Zählung der SAT Zuweisungen F .2n/22n/2poly(n,m)F

Jetzt sagen wir auf hoher Ebene, wie das Chargenbewertungsprotokoll durchzuführen ist. Wir möchten, dass der Beweis eine prägnante Darstellung der Schaltung ist, die sowohl für alle 2 k gegebenen Eingaben leicht zu bewerten als auch leicht zufällig zu verifizieren ist. Wir setzen den Beweis als ein univariates Polynom Q ( x ), das über ein ausreichend großes Erweiterungsfeld des Basisfeldes K (mit einer Eigenschaft von mindestens 2 n für unsere Anwendung) definiert ist, wobei Q ( x ) einen Grad von etwa 2 kd hat. und Q "skizziert" die Bewertung desC2kQ(x)K2nQ(x)2kdQ Arithmetikschaltungd über alle 2 k Zuordnungen. Das Polynom Q erfüllt zwei widersprüchliche Bedingungen:C2kQ

  • Der Verifizierer kann die Skizze , um die Wahrheitstabelle von C effizient zu erzeugen . Insbesondere wollen wir für einige explizit bekannte α i aus der Erweiterung von K ( Q ( α 0 ) , Q ( α 1 ) , , Q ( α K ) ) = ( C ( a 1 ) , , C ( a 2 K ) ) , wobei aQCαiK(Q(α0),Q(α1),,Q(αK))=(C(a1),,C(a2K))ai ist die te boolesche Zuweisung zu den k Variablen von C (unter einer gewissen Reihenfolge von Zuweisungen).ikC

  • Der Prüfer kann überprüfen, ob eine wahrheitsgetreue Darstellung des Verhaltens von C bei allen 2- k- Booleschen Zuweisungen in ungefähr 2- k + s- Zeit mit Zufälligkeit ist. Dies wird im Grunde genommen zu einem univariaten Polynomidentitätstest.QC2k2k+s

Die Konstruktion von verwendet einen Interpolationstrick, der aus den holographischen Beweisen stammt, wobei multivariate Ausdrücke effizient als univariate ausgedrückt werden können. Beide Elemente verwenden schnelle Algorithmen zum Manipulieren von univariaten Polynomen.Q

Ryan Williams
quelle
In der Mitte (oben) von Teil 2 auf Seite 6 sollte R (x) durch R (r) ersetzt werden.
Bitte senden Sie mir Kommentare zum Manuskript direkt; Ich überprüfe nicht jeden Tag den Stapelwechsel. Vielen Dank.
Ryan Williams
5
Könnten Sie die Hauptidee des Papiers zusammenfassen, um eine in sich geschlossene Antwort zu geben und möglicherweise vor Bit-Rot zu schützen?
Cody