El resumen del documento enuncia el resultado principal: para cada ε > 0 fijo hay constantes Cε y cε y un algoritmo determinista que decide 3-SAT con n variables y m cláusulas en como mucho Cε(n + m + 1)^cε · 2^(εn) operaciones de bit. El autor toma la ETH en su formulación habitual de tasa positiva: existe δ > 0 tal que ningún algoritmo determinista resuelve 3-SAT en tiempo 2^(δn)(n + m + 1)^O(1). Con ε = δ/2, el teorema la contradiría. Según el texto, es una versión simplificada de la prueba de OpenAI (referencia [1]) que combina sparsification, ocurrencias acotadas, sustitución espectral e interpolación racional.
La idea central es que, si las variables pudieran repartirse en grupos pequeños y cada cláusula usara un solo grupo, bastaría contar las asignaciones por grupo y multiplicar. Como las cláusulas enlazan grupos distintos, el autor elimina esos enlaces por vía algebraica. Cada cláusula se expresa con un polinomio que vale su valor de verdad en entradas booleanas, y cada ocurrencia de una variable se sustituye por una expresión lineal cuyos coeficientes dependen de un parámetro T. En T = 0 se recupera la variable original; en ciertos enteros positivos, cada factor depende de un único grupo y de unas pocas medidas lineales enteras.
Sumar el producto de los polinomios deformados sobre todas las asignaciones booleanas define un polinomio H(T), cuyo valor en cero es el número buscado de asignaciones satisfactorias. En los demás nodos enteros los valores pueden no ser positivos ni enteros, y se usan solo como datos de interpolación. El algoritmo calcula coeficientes de Taylor hasta un orden que es una pequeña fracción del número de variables, en cada entero elegido, e interpola para obtener H(0). La sección 2 muestra cómo una sustitución así da un algoritmo de conteo, la 3 la construye con matrices de intercambio que conmutan y la 4 fija los parámetros y la aritmética exacta.
El texto incluye dos reducciones previas. La primera es la sparsification de [3] (Corollary 1, p. 523): para cada η > 0, una fórmula 3-CNF se expresa como disyunción de como mucho 2^(ηn) fórmulas con a lo sumo Cη·n cláusulas cada una, en tiempo 2^(ηn) por un factor polinómico. La segunda, el Lema 1.3, da a cada ocurrencia de una variable su propia copia y fuerza la igualdad con un ciclo de implicaciones. Produce una fórmula equisatisfacible con N ≤ n + 3m variables, cada una en como mucho tres cláusulas, y con a lo sumo 4m cláusulas. La Proposición 1.4, para cada entero s ≥ 64, es el algoritmo determinista de conteo que se demuestra en las secciones siguientes, sin apoyarse en los nuevos lemas de [1].
Esta noticia la ha redactado una inteligencia artificial a partir de las fuentes citadas, con el criterio editorial de El Autómata (equilibrio, atribución y solo hechos publicados). Puede contener errores: consulta las fuentes originales. Modelo: claude-sonnet-5.5.