⚛️ quantum physics

Planted-solution SAT and Ising benchmarks from integer factorization

El artículo presenta una familia de instancias de referencia con solución plantada para solucionadores SAT y optimización Ising, derivadas de la factorización de enteros, que ofrecen un conjunto de pruebas escalable, estructurado y verificable donde el tiempo de ejecución mediano crece exponencialmente con la longitud de los factores.

Autores originales: Itay Hen

Publicado 2026-04-14

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Itay Hen

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

¡Hola! Imagina que quieres poner a prueba la inteligencia de un superordenador, pero no quieres usar acertijos aleatorios que no tengan sentido. Quieres un rompecabezas que sea lógico, estructurado y del cual ya conoces la solución.

Este artículo presenta una nueva forma de crear esos rompecabezas, basándose en algo que todos hemos hecho en la escuela: multiplicar números.

Aquí te explico la idea central con analogías sencillas:

1. La Idea Principal: El "Rompecabezas de la Multiplicación"

Imagina que tienes dos números secretos, llamémosles P y Q (son números primos, como piezas de un rompecabezas que no se pueden dividir más). Si los multiplicas, obtienes un número grande N.

El problema normal: Si te doy el número N (digamos, 143) y te pregunto "¿qué dos números multiplicados dan 143?", es difícil encontrar la respuesta (11 y 13).
El truco de los autores: En lugar de intentar adivinar, ellos construyen el problema al revés. Ellos eligen primero los números secretos (11 y 13), hacen la multiplicación y luego crean un "plan de construcción" (un código lógico) que obliga a cualquier computadora a encontrar esos números exactos para que la multiplicación tenga sentido.

Es como si un arquitecto construyera una casa, guardara las llaves (la solución), y luego creara un laberinto donde la única salida posible es llegar a esas llaves.

2. ¿Cómo funciona el "Laberinto"? (La Analogía de la Fábrica de Agua)

Para convertir la multiplicación en un problema que una computadora pueda resolver, los autores la transforman en una serie de reglas lógicas (como un circuito eléctrico).

Imagina una fábrica de agua donde tienes dos tuberías de entrada (los números P y Q) y quieres que salga un chorro de agua específico en la salida (el número N).

Los "Desagües" (Carriles): La multiplicación se hace columna por columna.
El problema de las "Inundaciones" (Llevadas o Carries): Cuando sumas números en una columna, a veces sobra agua (una "llevada") que tiene que pasar a la siguiente columna.
- En una multiplicación normal, si sobra agua en la columna 1, pasa a la columna 2, que ya tenía su propia agua, y ahora se desborda aún más hacia la 3.
- Aquí está la magia: Esta "inundación" viaja a través de toda la fábrica. Un pequeño cambio en el principio afecta al final. Esto crea una red de conexiones muy larga y compleja.

Los autores descubrieron que a medida que los números son más grandes (más dígitos), esta red de conexiones crece de forma explosiva (como una bola de nieve rodando por una montaña). Si duplicas el tamaño de los números, la complejidad del laberinto no se duplica, ¡se cuadruplica y mucho más!

3. ¿Por qué es un buen examen? (El "Cheat Sheet" Perfecto)

En el mundo de las pruebas de inteligencia artificial, hay dos tipos de problemas:

Problemas aleatorios: Son como tirar dados. Son difíciles, pero no sabes si la computadora falló porque el problema era imposible o porque el programa es tonto.
Problemas "plantados" (Planted Solutions): Aquí, los autores ya saben la respuesta porque ellos la pusieron ahí.

La ventaja: Si la computadora resuelve el problema, verificas instantáneamente si lo hizo bien comparando su respuesta con la que ellos ya tenían guardada. No hay dudas. Es como un examen donde el profesor tiene el solucionario en la mano.

4. ¿Qué descubrieron al probarlo?

Pusieron a trabajar a los mejores "detectives" de computadoras (llamados solucionadores SAT) contra estos rompecabezas de multiplicación.

El resultado: A medida que aumentaban el tamaño de los números (de 8 dígitos a 27 dígitos), el tiempo que tardaban las computadoras en resolverlo se duplicaba con cada nuevo dígito.
La analogía: Es como si cada vez que añades una pieza más al rompecabezas, el tiempo para terminarlo se duplicara. Esto significa que para números muy grandes, incluso las computadoras más potentes tardarían años o siglos.

5. ¿Para qué sirve esto?

Los autores no están intentando hackear bancos (aunque la factorización de números es la base de la seguridad bancaria). Lo que hacen es crear un banco de pruebas controlado.

Sirve para medir qué tan inteligentes son las nuevas computadoras cuánticas y clásicas.
Sirve para ver si los algoritmos pueden manejar problemas que tienen una estructura lógica real (como las matemáticas) y no solo caos aleatorio.
Tienen un software de código abierto para que cualquiera pueda generar sus propios niveles de dificultad.

En resumen

Los autores han creado una máquina generadora de rompecabezas matemáticos.

Eligen dos números secretos.
Construyen un laberinto lógico basado en cómo se multiplican esos números.
Saben la salida exacta (la solución).
Desafían a las computadoras a encontrar el camino.

Lo genial es que este laberinto tiene una estructura muy especial: está lleno de "corrientes" que conectan el principio con el final, haciendo que sea extremadamente difícil de navegar, pero perfectamente verificable si llegas a la meta. Es una herramienta perfecta para medir el verdadero poder de cálculo de la próxima generación de inteligencias artificiales.

Resumen Técnico: Instancias de Solución Plantada para SAT y Ising Derivadas de la Factorización de Enteros

Autores: Itay Hen (Instituto de Ciencias de la Información, USC; Departamento de Física y Astronomía, USC).

1. Problema Abordado

El campo de la satisfacción de restricciones (SAT) y la optimización de Ising carece de familias de instancias de referencia (benchmarks) que cumplan simultáneamente tres criterios fundamentales:

Estructura realista: Que reflejen la complejidad de problemas computacionales reales (no puramente aleatorios).
Escalabilidad sistemática: Que permitan controlar el tamaño y la dificultad mediante un parámetro único.
Verificabilidad de la solución: Que posean una "verdad fundamental" (ground truth) conocida para validar la salida de los solucionadores.

Las ensembles aleatorias (como k-SAT uniforme) carecen de una solución conocida para validación, mientras que las instancias de competiciones suelen carecer de un control preciso sobre la dificultad. Además, la mayoría de las construcciones de soluciones plantadas existentes se basan en desorden aleatorio o plantado algebraico, ignorando las correlaciones de largo alcance deterministas típicas de problemas aritméticos.

2. Metodología

El autor propone una nueva familia de instancias de "solución plantada" derivada de la factorización de enteros. El proceso de construcción sigue un pipeline de tres etapas:

A. Codificación Aritmética:
Dado dos números primos $p$ y $q$ de $d$ bits, se define $N = p \times q$ . El objetivo es codificar las restricciones aritméticas de la multiplicación binaria en una fórmula en Forma Normal Conjunta (CNF).
- Se generan productos parciales ( $p_i \land q_j$ ) que se colocan en columnas de una tabla de multiplicación.
- Se aplican contracciones iterativas usando sumadores de medio bit (half-adders): la suma de dos entradas en una columna genera una variable de suma (XOR) y una de acarreo (AND) que se propaga a la siguiente columna.
- Los bits conocidos de $N$ actúan como restricciones de fijación (pinning constraints) en las columnas finales.
B. Preprocesamiento Lógico:
Antes de convertir a CNF, se aplica un bucle de reducción lógica iterativa que incluye:
- Propagación de valores fijos (pinning).
- Simplificación de cláusulas AND y XOR (plegado de constantes, identificación de variables).
- Inferencia entre cláusulas compartidas.
- Fusión de variables equivalentes mediante una estructura de datos union-find.
  Esto reduce drásticamente el número de variables y cláusulas, especialmente para tamaños pequeños, aunque la proporción de reducción disminuye a medida que $d$ crece.
C. Salida y Compilación:
- SAT: Las cláusulas residuales se convierten a formato DIMACS CNF estándar.
- Ising: El sistema de restricciones se compila en un Hamiltoniano de Ising cuadrático. Las cláusulas AND y XOR se mapean a "gadgets" de energía (penalizaciones) que son cero en la solución válida y positivos en las inválidas. Esto introduce espines auxiliares para las cláusulas XOR, permitiendo una representación puramente cuadrática.

3. Contribuciones Clave

Estructura de Correlaciones de Largo Alcance: A diferencia de los problemas SAT aleatorios, esta construcción introduce correlaciones inducidas por los acarreos (carries) que se propagan a través de columnas distantes. Un cambio en un bit de bajo orden puede afectar acarreos que viajan hasta columnas de orden $d^2$ .
Escalabilidad Cuártica ( $\Theta(d^4)$ ): Se demuestra analíticamente que el número total de contracciones (y por ende, de variables y cláusulas) crece como $d^4$ . Esto se debe a que la población de entradas en las columnas crece cuadráticamente ( $\sim d^2$ ) debido a la cascada de acarreos, y sumar esto sobre $\sim d^2$ columnas da como resultado un total cuártico.
Verificabilidad y Dualidad: La solución plantada $(p, q)$ es conocida por diseño, permitiendo una verificación inequívoca. Además, el mismo problema se puede resolver tanto mediante solucionadores SAT como optimizadores clásicos/cuánticos de Ising, facilitando comparaciones cruzadas.
Software de Código Abierto: Se proporciona un generador de software que produce estas instancias de manera determinista controlada por un solo parámetro ( $d$ ).

4. Resultados Empíricos

Escalado de Tiempo de Ejecución: Se realizaron pruebas con solucionadores SAT de vanguardia (Kissat 3.0 y CaDiCaL 1.5) para longitudes de bits $d$ $d$ entre 8 y 27.
- El tiempo de ejecución mediano crece exponencialmente con la longitud de los factores ( $T \sim 2^{\beta d}$ ).
- Se observó que cada bit adicional duplica aproximadamente el tiempo de ejecución ( $\beta \approx 1$ ).
- Ambos solucionadores mostraron pendientes casi idénticas, lo que sugiere que la dificultad es inherente a la estructura del circuito de multiplicación y no a heurísticas específicas del solucionador.
Dificultad Creciente: Para $d=27$ ( $N \approx 10^{16}$ ), los tiempos medianos alcanzaron $\sim 10^4$ segundos, indicando que instancias con $d \ge 35-40$ serán pruebas de estrés significativas para los solucionadores modernos.
Análisis de la Red de Interacción (Ising): El grafo de interacción del modelo de Ising resultante presenta una distribución de grados heterogénea (los espines de acarreo en columnas centrales tienen grados altos, $\sim d^2$ ) y bordes de largo alcance, simulando una conectividad de "mundo pequeño" ausente en modelos de red local.

5. Significado e Impacto

Esta investigación introduce un nuevo régimen de benchmarks que complementa a las familias existentes:

Puente entre Aritmética y Complejidad Computacional: Convierte un problema aritmético clásico (factorización) en un problema de satisfacción de restricciones con una estructura determinista rica y verificable.
Herramienta para Optimización Cuántica y Clásica: Al ofrecer una compilación directa a Ising, permite probar el rendimiento de máquinas de Ising (incluyendo annealers cuánticos) en problemas con correlaciones de largo alcance, un escenario donde los algoritmos aleatorios suelen fallar o comportarse de manera diferente.
Validación de Solucionadores: Proporciona un entorno controlado para estudiar cómo los solucionadores manejan la estructura no aleatoria y las dependencias de largo alcance, algo crucial para el desarrollo de futuros algoritmos de optimización.

En resumen, el trabajo de Hen ofrece una metodología robusta para generar instancias de prueba escalables, estructuradas y verificables, llenando un vacío crítico en la evaluación de solucionadores SAT y optimizadores de Ising.