¿Cómo se demuestra que la versión MA de SETH es falsa?

Según este artículo , que analiza una extensión no determinista de la hipótesis del tiempo exponencial fuerte (SETH), "[…] Williams ha mostrado recientemente que las hipótesis relacionadas sobre la complejidad de Merlin-Arthur de k-TAUT son falsas". Sin embargo, ese documento solo cita una comunicación personal.

¿Cómo se demuestra que la versión MA de SETH es falsa?

Sospecho que implica algebrizar la fórmula, pero no tengo más idea.

Puede encontrar una preimpresión siguiendo este enlace http://eccc.hpi-web.de/report/2016/002/

EDITAR (1/24) A pedido, aquí hay un resumen rápido, tomado del propio documento, pero que pasa por alto muchas cosas. Supongamos Merlin puede llegar a Arthur que para un circuito -Variable aritmética C , su valor en todos los puntos en { 0 , 1 } k es una cierta tabla de 2 k elementos de campo, en el tiempo sobre ( s + 2 k ) ⋅ d , donde s es el tamaño de C y d es el grado del polinomio calculado por $k$$C$$\{0,1\}^k$$2^k$$(s + 2^k) \cdot d$$s$$C$$d$$C$. (Llamamos a esto una "prueba breve no interactiva de evaluación por lotes" --- evaluar en muchas tareas).$C$

Entonces Merlín puede resolver SAT para Arthur de la siguiente manera. Dado un CNF F sobre n variables y m cláusulas, Merlin y Arthur primero construyen un circuito aritmético C sobre n / 2 variables de grado como máximo m n , tamaño de m n ⋅ 2 n / 2 , que toma una suma sobre todas las asignaciones a las primeras n / 2 variables del CNF F (agregando un 1 a la suma cuando F es verdadero y $\#$$F$$n$$m$$C$$n/2$$mn$$mn \cdot 2^{n/2}$$n/2$$F$$1$$F$$0$cuando es falso) Utilizando el protocolo de evaluación por lotes, Merlín puede demostrar que adquiere 2 n / 2 valores particulares en todas sus asignaciones booleanas de 2 n / 2 , en aproximadamente 2 n / 2 p o l y ( n , m ) tiempo. Resumiendo todos esos valores, obtenemos el recuento de las asignaciones a SAT F .$C$$2^{n/2}$$2^{n/2}$$2^{n/2} poly(n,m)$$F$

Ahora decimos a alto nivel cómo hacer el protocolo de evaluación por lotes. Queremos que la prueba sea una representación sucinta del circuito que sea fácil de evaluar en todas las entradas de 2 k dadas, y también fácil de verificar con aleatoriedad. Establecemos que la prueba es un polinomio univariado Q ( x ) definido sobre un campo de extensión suficientemente grande del campo base K (de característica al menos 2 n para nuestra aplicación), donde Q ( x ) tiene un grado de aproximadamente 2 k ⋅ d , y Q `` bosqueja '' la evaluación del título$C$$2^k$$Q(x)$$K$$2^n$$Q(x)$$2^k \cdot d$$Q$ circuito aritmético C sobre las 2 k asignaciones. El polinomio Q satisface dos condiciones en conflicto:$d$$C$$2^k$$Q$

• El verificador puede utilizar el esquema para producir de manera eficiente la tabla de verdad de C . En particular, para algunos α i explícitamente conocidos de la extensión de K , queremos ( Q ( α 0 ) , Q ( α 1 ) , ... , Q ( α K ) ) = ( C ( a 1 ) , ... , C ( a 2 K ) ) , donde $Q$$C$$\alpha_i$$K$$(Q(\alpha_0), Q(\alpha_1),\ldots,Q(\alpha_K)) = (C(a_1),\ldots,C(a_{2^K}))$ es la i ésima asignación booleana a las k variables de C (bajo algún orden en asignaciones)$a_i$$i$$k$$C$

• El verificador puede verificar que es una representación fiel del comportamiento de C en todas las asignaciones booleanas de 2 k , en aproximadamente 2 k + s , con aleatoriedad. Básicamente, esto se convierte en una prueba de identidad polinómica univariante.$Q$$C$$2^k$$2^k + s$

La construcción de utiliza un truco de interpolación que se origina en las pruebas holográficas, donde las expresiones multivariadas pueden `` expresarse '' de manera eficiente como univariadas. Ambos elementos utilizan algoritmos rápidos para manipular polinomios univariados.$Q$