💻 computer science

SAT Certificates for the Matrix-Multiplication Challenges over F2: All Ten `Expected-UNSAT` Instances Are Satisfiable, and a Type-3-Free Rank-23 Scheme

Este artículo demuestra que las diez fórmulas de multiplicación de matrices de rango 23 sobre $\mathbb{F}_2$ previamente "esperadas-insatisfechas" son en realidad satisfacibles y proporciona certificados completos para estas instancias junto con un nuevo esquema de rango 23 que contiene un sumando libre de tipo 3.

Autores originales: Nick Palladinos

Publicado 2026-08-03

📖 7 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Nick Palladinos

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando resolver un rompecabezas de tres dimensiones masivo. Pero este no es el dibujo de un atardecer o un gato; es una máquina matemática diseñada para multiplicar dos cuadrículas de números. En el mundo de la informática y las matemáticas, esto se llama "multiplicación de matrices". Durante décadas, los matemáticos han buscado la forma más eficiente de construir esta máquina. Quieren saber el número mínimo absoluto de piezas básicas y diminutas (llamadas "multiplicaciones") necesarias para que todo funcione.

Piensa en estas piezas de construcción como si fueran ladrillos de LEGO. Durante mucho tiempo, todos sabían que podíamos construir una máquina de multiplicación de 3x3 usando 23 ladrillos. La gran pregunta era: ¿Podemos hacerlo con solo 22? Para averiguarlo, los investigadores convirtieron el problema en un gigantesco acertijo lógico, similar a los que podrías encontrar en un videojuego o en un libro de Sudoku, pero a una escala que te haría dar vueltas la cabeza. Codificaron las reglas de la matemática en un formato que las computadoras pudieran verificar, creando un problema "SAT" (que significa "Satisfacibilidad"). Si la computadora puede encontrar una manera de poner todos los interruptores en "encendido" sin romper ninguna regla, el acertijo está resuelto. Si la computadora dice "imposible", entonces tal vez 23 ladrillos no sean suficientes. Este artículo profundiza en un conjunto específico de estos acertijos lógicos que fueron diseñados para probar los límites de nuestras computadoras actuales y de nuestra comprensión de estas máquinas matemáticas.

El gran acertijo "imposible" que no lo era

Conoce a Nick Palladinos, un detective digital que decidió echar un vistazo fresco a un conjunto de diez acertijos lógicos a los que todos los demás habían dado la espalda. Estos acertijos, conocidos como las instancias del "Desafío 2", fueron construidos por otros investigadores con un conjunto de reglas muy específico y rígido. Los creadores de estos acertijos creían que eran "imposibles" de resolver. Pensaban que las reglas eran tan estrictas que ninguna combinación de 23 ladrillos de LEGO podría encajar para construir la máquina. Era como si te dijeran: "Aquí hay una caja con una cerradura que definitivamente no se puede abrir", y todos simplemente asentían y se marchaban.

Pero Palladinos no se limitó a intentar forzar la cerradura con un martillo más grande. En su lugar, observó la cerradura misma y se dio cuenta de algo crucial: las reglas no eran tan estrictas como todos pensaban.

Los creadores de los acertijos habían escrito las reglas usando instrucciones "positivas". Decían: "Debes tener este ladrillo específico aquí", y "Debes tener aquel ladrillo allá". Pero olvidaron decir: "Y no puedes tener ningún otro ladrillo tocando estos". Resulta que la matemática permite añadir ladrillos extra, siempre y cuando la máquina final siga funcionando correctamente. Los acertijos "imposibles" en realidad solo estaban esperando a que alguien se diera cuenta de que la puerta no estaba cerrada con llave; era solo que todos intentaban encajar las piezas del rompecabezas en una caja que era demasiado pequeña, ignorando el hecho de que la caja en realidad podía ser un poco más grande.

La magia de desplazar y permutar

Entonces, ¿cómo resolvió Palladinos estos acertijos? Utilizó un truco ingenioso que involucra la "simetría". Imagina que tienes un Cubo de Rubik. Si giras todo el cubo o lo rotas, los colores se mueven, pero el cubo sigue siendo el mismo objeto. Palladinos se dio cuenta de que la "máquina" matemática que estaba construyendo tenía una propiedad similar. Podía tomar una solución que funcionara (un conjunto de 23 ladrillos que multiplican matrices con éxito) y girar, rotar o barajar las piezas alrededor usando una danza matemática especial llamada "acción de grupo GL(3, 2)".

Piensa en ello como si estuvieras reordenando los muebles de una habitación. Puedes mover el sofá a la izquierda, la lámpara a la derecha y la alfombra en el medio. La habitación sigue siendo una habitación, y los muebles siguen funcionando, pero la disposición es diferente. Palladinos tomó una solución conocida que funcionaba y aplicó estos "giros" matemáticos. Luego, utilizó un juego de correspondencia para ver si estas nuevas versiones barajadas de los muebles podían encajar en los "espacios" requeridos por los complicados acertijos.

¡Y adivina qué! ¡Encajaron perfectamente!

De hecho, Palladinos no solo encontró una solución; encontró soluciones para todos los diez acertijos que supuestamente eran imposibles. Demostró que estas fórmulas "irresolubles" son en realidad satisfacibles. La computadora no solo adivinó; verificó cada una de las reglas. El artículo confirma que para los 10 archivos del "Desafío 2", existe una forma válida de disponer los 23 bloques de construcción para que la máquina funcione. La etiqueta de "imposible" fue un malentendido de las reglas, no una verdadera barrera matemática.

El ladrillo "fantasma" y la solución perfecta

El artículo también abordó un tercer desafío, el "Desafío 3". Este planteaba una pregunta diferente: ¿Podemos construir la máquina usando 23 ladrillos, pero asegurándonos de que un ladrillo específico sea "fantasmagórico"? En lenguaje matemático, esto significa que uno de los 23 bloques de construcción debe tener un "conteo de tipo-3" de cero. Esta es una forma elegante de decir que uno de los ladrillos no debería participar en un patrón específico y común que suele aparecer en estas máquinas.

Palladinos también logró hacer esto. Comenzó con una solución que funcionaba y realizó un intercambio pequeño y preciso. Tomó dos ladrillos que estaban haciendo un trabajo específico y los reemplazó por otros dos ladrillos diferentes que hacían exactamente el mismo trabajo pero se veían distintos. Este intercambio fue tan ingenioso que creó un ladrillo "fantasma": uno que no activó el patrón prohibido en absoluto. Demostró que, de hecho, se puede construir la máquina de multiplicación de matrices 3x3 con 23 ladrillos, donde uno de ellos está completamente libre de ese patrón específico.

La comprobación final

Para asegurarse de que nadie pudiera decir: "Oh, simplemente tuviste suerte con la computadora", Palladinos construyó un verificador súper estricto. Generó la lista completa de 26,541 variables (los interruptores) para los 21 acertijos (10 del Desafío 1, 10 del Desafío 2 y 1 del Desafío 3). Luego ejecutó un programa separado que leía las reglas originales del acertijo y las nuevas soluciones, verificando cada una de las 2,461,316 cláusulas lógicas.

¿El resultado? Cero fallos. Cada una de las reglas se cumplió. Las soluciones son reales, están verificadas y son reproducibles. Cualquier persona con el software adecuado puede ejecutar el mismo código y obtener exactamente la misma respuesta en unos nueve segundos.

Qué significa (y qué no significa)

Entonces, ¿cuál es la gran conclusión? El artículo muestra que los acertijos "imposibles" eran en realidad resolubles todo el tiempo; las reglas simplemente no eran tan estrictas como los creadores de los acertijos pensaban. Es un recordatorio de que en las matemáticas y la informática, a veces la parte más difícil no es encontrar la solución, sino darse cuenta de que el problema no está tan roto como parece.

Sin embargo, hay un detalle. Este artículo resuelve los acertijos para un tipo específico de mundo matemático llamado "F2" (que es como un mundo donde los números solo dan la vuelta después de 1, así que 1+1=0). No demuestra que podamos construir una máquina de 22 ladrillos. La búsqueda de la máquina de 22 ladrillos (Desafío 4) sigue abierta. El artículo tampoco dice que estas soluciones funcionen para cualquier tipo de matemática que puedas usar en el mundo real, como los números complejos utilizados en ingeniería. Solo resuelve los acertijos lógicos específicos tal como fueron escritos.

Pero para los acertijos que fueron escritos, el veredicto es claro: lo "imposible" es en realidad posible. La puerta nunca estuvo cerrada con llave; solo necesitábamos la llave adecuada para girar el pomo.

Resumen Técnico: Certificados SAT para los Desafíos de Multiplicación de Matrices sobre $\mathbb{F}_2$

Planteamiento del Problema
Este documento aborda el benchmark de satisfacción de la multiplicación de matrices SAT establecido por Heule, Kauers y Seidl, que codifica la búsqueda de algoritmos bilineales de rango 23 para la multiplicación de matrices de $3 \times 3$ sobre el cuerpo finito $\mathbb{F}_2$ . El benchmark consta de tres familias principales de desafíos:

Desafío 1: Diez fórmulas declaradas como satisfactorias pero históricamente difíciles para los resolvedores SAT generales.
Desafío 2: Diez fórmulas que contienen emparejamientos codificados de monomios de "tipo-3" (términos de multiplicación de matrices estándar), que se conjeturó que eran insatisfactibles (UNSAT).
Desafío 3: Una única fórmula que pregunta si puede existir un esquema de rango 23 donde un sumando específico contenga cero monomios de tipo-3.

El objeto matemático central es la descomposición del tensor de multiplicación de matrices $3 \times 3$ en 23 sumandos de rango uno, que satisfacen 729 ecuaciones de Brent cúbicas. Estas ecuaciones se codifican en Forma Normal Conjuntiva (CNF) mediante variables de Tseitin, lo que resulta en instancias con 26,541 variables y más de 2.4 millones de cláusulas.

Metodología
El autor emplea un enfoque de "búsqueda local semántica" que opera sobre las 621 variables base (las entradas de las matrices de coeficientes $A_t, B_t, C_t$ ) en lugar del conjunto completo de variables CNF. La metodología procede en tres fases distintas:

Búsqueda Semántica y Caminata Residual: El algoritmo mantiene un tensor "residual" (la diferencia entre la suma actual de tensores de rango uno y el tensor objetivo). Realiza una caminata de dos fases:
- Reparación Directa: Invierte bits que corrigen inmediatamente un defecto residual específico.
- Ganancia/Activación: Permite movimientos que pueden aumentar temporalmente el peso residual si preparan el tensor para una cancelación futura, puntuados por el cambio en el peso de Hamming residual (break - make).
  Una vez que se encuentra un estado de residuo cero semánticamente, se asignan las 621 variables base y se utiliza la propagación de unidad para determinar las 25,920 variables auxiliares de Tseitin restantes.
Simetría y Transformación (Desafío 2): Para las instancias de "esperado-UNSAT", el documento demuestra que las restricciones CNF solo imponen la presencia de incidencias específicas de tipo-3 mediante cláusulas unitarias positivas, en lugar de imponer una exclusión exacta de otras. Para construir testigos:
- El autor utiliza la acción isotrópica $GL(3, 2)^3$ para transformar esquemas conocidos de 23 sumandos exactos.
- Se aplica la simetría de traza cíclica $(A, B, C) \to (B, C, A)$ .
- Un algoritmo de emparejamiento perfecto asigna los sumandos transformados a los espacios restringidos definidos por las cláusulas unitarias positivas.
Reparación Bloqueada e Identidad (Desafío 3): Para satisfacer la condición de un sumando libre de tipo-3:
- El autor fija tres términos específicos de una solución semilla.
- Se aplica una identidad de preservación de rango sobre $\mathbb{F}_2$ : $92 \otimes 89 + 438 \otimes 24 = 92 \otimes 65 + 490 \otimes 24$ . Esta operación reemplaza dos sumandos con otros dos mientras preserva la suma total del tensor, permitiendo que un sumando sea reconfigurado para tener cero monomios de tipo-3.

Contribuciones Clave y Resultados
El documento proporciona certificados SAT completos e independientemente verificables para las 21 instancias en el repositorio del benchmark (commit 150b2e2f):

Desafío 1: Todas las 10 instancias se resuelven mediante búsqueda local semántica. Las soluciones se generan en segundos, demostrando que la dificultad para los resolvedores generales proviene de la codificación de Tseitin y no de la geometría tensorial subyacente.
Desafío 2: Todas las 10 instancias, anteriormente conjeturadas como UNSAT, se demuestran satisfactorias. El documento revela que los emparejamientos "codificados" no eran núcleos exactos; las fórmulas permitían incidencias de tipo-3 adicionales siempre que la paridad total fuera correcta. Los testigos construidos tienen incidencias de tipo-3 totales que oscilan entre 41 y 93, en lugar de las 27 esperadas.
Desafío 3: Se construye una descomposición de rango-23 válida donde un sumando tiene un conteo de tipo-3 de cero. Esto satisface la restricción específica del CNF del Desafío-3.
Verificación: Un analizador y evaluador de cláusulas separado verificó de forma independiente todos los modelos de los 21 casos. El proceso de verificación revisó 557,361 variables asignadas y 2,461,316 cláusulas con cero fallos. Un reproductor de Python determinista regenera todos los certificados en aproximadamente nueve segundos.

Significado
La principal significancia del documento radica en resolver el valor de verdad de los archivos CNF específicos proporcionados en el benchmark. Establece que:

Las fórmulas del Desafío-2, "esperado-UNSAT", son satisfactorias porque sus restricciones son inclusivas (unidades positivas) en lugar de exclusivas (núcleos exactos).
El grupo de simetría del tensor y la estructura semántica permiten la construcción de testigos que los resolvedores CDCL genéricos no logran encontrar eficientemente.
Es posible lograr un sumando libre de tipo-3 dentro de un esquema de rango-23.

El trabajo establece explícitamente que no resuelve la cuestión del rango-22 (Desafío 4) ni pretende proporcionar algoritmos no conmutativos sobre anillos arbitrarios. La contribución se limita estrictamente a la satisfacción de las codificaciones booleanas proporcionadas y a la demostración de un flujo de construcción semántica que elude las limitaciones de la resolución SAT pura en estas instancias específicas. El autor reconoce el uso de OpenAI GPT-5.6 Sol para la exploración computacional, pero enfatiza que las afirmaciones matemáticas se fundamentan en los artefactos verificables de forma independiente.

El gran acertijo "imposible" que no lo era

La magia de desplazar y permutar

El ladrillo "fantasma" y la solución perfecta

La comprobación final

Qué significa (y qué no significa)

Más como este