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

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.

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 Polynoms$k$$C$$\{0,1\}^k$$2^k$$(s + 2^k) \cdot d$$s$$C$$d$$C$. (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 $\#$$F$$n$$m$$C$$n/2$$mn$$mn \cdot 2^{n/2}$$n/2$$F$$1$$F$$0$ wenn es falsch ist). Mit dem Chargenbewertungsprotokoll kann Merlin dann nachweisen, dass 2 n / 2 annimmt$C$$2^{n/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 .$2^{n/2}$$2^{n/2} poly(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 k ⋅ d hat. und Q "skizziert" die Bewertung des$C$$2^k$$Q(x)$$K$$2^n$$Q(x)$$2^k \cdot d$$Q$ Arithmetikschaltung$d$ über alle 2 k Zuordnungen. Das Polynom Q erfüllt zwei widersprüchliche Bedingungen:$C$$2^k$$Q$

• 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 $Q$$C$$\alpha_i$$K$$(Q(\alpha_0), Q(\alpha_1),\ldots,Q(\alpha_K)) = (C(a_1),\ldots,C(a_{2^K}))$$a_i$ ist die te boolesche Zuweisung zu den k Variablen von C (unter einer gewissen Reihenfolge von Zuweisungen).$i$$k$$C$

• 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.$Q$$C$$2^k$$2^k + 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$