Revisiting Incremental Linearization for Nonlinear Integer Arithmetic

Imagina que eres un detective intentando resolver un misterio, pero las pistas que recibes están escritas en un lenguaje que cambia su significado dependiendo de cómo las mires. Este es el mundo de la Satisfacibilidad Modular de Teorías (SMT), una rama de la informática donde el software intenta averiguar si un conjunto de reglas lógicas puede ser verdadero al mismo tiempo. Piensa en esto como un solucionador de acertijos superinteligente que comprueba si un programa fallará, si se puede romper un código secreto o si la ruta de un robot es segura.

La mayoría de las veces, estos acertijos son fáciles porque solo involucran líneas rectas y sumas simples (como $x + y = 5$). Las computadoras son asombrosas en esto. Pero la vida se vuelve caótica cuando introduces la aritmética no lineal—reglas donde las cosas se multiplican entre sí o se elevan a potencias (como $x \times y$ o $x^3$). De repente, las reglas se curvan y se retuercen, y las matemáticas se vuelven increíblemente difíciles de resolver. De hecho, para los números enteros, es matemáticamente imposible crear un método perfecto y 100% completo que resuelva todos estos acertijos. Debido a esto, los científicos de la computación construyen detectives "suficientemente buenos" que utilizan trucos ingeniosos para encontrar respuestas rápidamente, incluso si no pueden prometer resolver cada caso imposible.

El artículo que estás a punto de leer presenta a un nuevo detective, llamado qfn2l, que es mejor resolviendo estos complicados acertijos curvos que los que teníamos antes. Los autores, investigadores de la Universidad Técnica Checa en Praga, se dieron cuenta de que los viejos atajos tenían dificultades con un tipo específico de acertijo difícil: aquellos que involucran potencias (como $x^3$) y productos mixtos (como $x^2y$). Decidieron mejorar el kit de herramientas del detective con un nuevo conjunto de reglas que actúan como una red más apretada, atrapando las malas conjetras que solían escaparse.

La vieja forma: Adivinar con funciones no interpretadas

Para entender la actualización, veamos cómo trabajaban los detectives anteriores. Imagina que tienes una caja misteriosa etiquetada como $f(x, y)$. No sabes qué hay dentro, pero sabes que si introduces los mismos números, obtienes el mismo número. El método antiguo trataba cada multiplicación, como $x \times y$, como esta caja misteriosa. La computadora adivinaba un valor para la caja, comprobaba si tenía sentido y, si no era así, añadía una regla para corregir la conjetura.

Esto funcionaba bien para casos simples, pero era como intentar adivinar el peso de una sandía sabiendo solo que es "pesada". Era demasiado vago. Cuando el acertijo involucraba potencias altas, como $x^3$, las reglas antiguas eran demasiado laxas. El detective hacía una conjetura, la computadora decía: "No, eso no encaja", y luego añadía una regla muy débil para corregirlo. El detective tenía que adivinar, fallar y volver a adivinar cientos de veces, a menudo quedándose sin tiempo antes de encontrar la respuesta.

El nuevo truco: Apretar la red con secantes

Los autores de este artículo decidieron dejar de tratar estas potencias como cajas misteriosas y, en su lugar, tratarlas como constantes frescas—simples números que representan el resultado de la potencia. Pero la verdadera magia reside en las nuevas reglas que añadieron para verificar estos números.

Descubrieron que para cualquier número entero, digamos $v$, la función $x^k$ (como $x^3$) se comporta de manera muy predecible entre $v$ y $v+1$. Crearon un nuevo conjunto de reglas basadas en rectas secantes. Imagina una curva en un gráfico. Una recta secante es una línea recta que conecta dos puntos en esa curva. Los autores se dieron cuenta de que si dibujas una línea recta entre el punto $(v, v^k)$ y el siguiente punto entero, esa línea crea una "valla" muy ajustada alrededor de la curva.

Aquí está la analogía:

• La vieja forma: El detective dibujaba un círculo enorme y holgado alrededor de las posibles respuestas. Era fácil de dibujar, pero permitía la entrada de muchas conjetras erróneas.
• La nueva forma: El detective dibuja una serie de vallas rectas y ajustadas que abrazan la curva de la respuesta muy de cerca. Si una conjetra cae fuera de estas vallas ajustadas, el detective sabe inmediatamente que es errónea y añade una regla para empujar la conjetra de vuelta al interior.

Debido a que estas vallas son tan ajustadas, el detective no tiene que adivinar tantas veces. Converge en la respuesta correcta mucho más rápido, especialmente en acertijos que involucran cubos y productos mixtos.

El desafío de la "Suma de tres cubos"

Para demostrar que su nuevo detective funcionaba, los autores lo probaron en una famosa clase de acertijos llamada la "suma de tres cubos". Estos son problemas que preguntan: "¿Puedes encontrar tres números enteros que, al elevarlos al cubo y sumarlos, den un número específico?".

Por ejemplo, el acertijo podría ser: $x^3 + y^3 + z^3 = 79$.

Este es un suplicio para los solucionadores estándar. Los números pueden ser enormes y las relaciones son complejas. Los autores probaron su nuevo solucionador, qfn2l, contra los mejores solucionadores existentes (como Z3, cvc5 y MathSAT).

• Los otros solucionadores intentaron resolver el acertijo $x^3 + y^3 + z^3 = 79$ pero se rindieron tras 3 minutos (se "agotó el tiempo").
• El nuevo solucionador, qfn2l, encontró la respuesta—$x = -19, y = 35, z = -33$—en solo 20 segundos.

Los resultados: Un nuevo competidor de alto nivel

Los investigadores ejecutaron su solucionador en una colección masiva de 25,444 acertijos de una biblioteca estándar llamada SMT-LIB. Esto es lo que encontraron:

1. Rendimiento general: El nuevo solucionador es competitivo con las mejores herramientas actuales. Resolvió unos 14,000 acertijos en total, lo cual es cercano a los mejores desempeños, aunque no superó a los mejores (como Z3) en cada tipo de acertijo.
2. El punto ideal: El nuevo solucionador brilla absolutamente en los acertijos dominados por potencias y productos mixtos. En la familia "MathProblems" (que incluye la suma de cubos), resolvió aproximadamente el 53% de las instancias (585 a 587 de 1,100). Los otros solucionadores tuvieron dificultades significativamente mayores con estos tipos específicos de problemas.
3. El compromiso: Los autores probaron una versión de su solucionador que intentaba ser extra cuidadosa al verificar si las diferentes partes del acertijo eran consistentes (llamado "axiomas de congruencia"). Descubrieron que esta verificación extra en realidad ralentizaba al solucionador en acertijos generales, resolviendo aproximadamente 1,600 instancias menos en total. Esto sugiere que para la mayoría de los problemas, las vallas ajustadas (límites secantes) son suficientes y no necesitas el trabajo pesado adicional de verificar cada regla de consistencia.

Por qué esto es importante

El artículo no pretende haber resuelto lo irresoluble. Admiten que, debido a que el problema es matemáticamente indecidible, ninguna computadora puede resolver todos los casos. Sin embargo, han demostrado que al cambiar la forma en que aproximamos estas reglas curvas y no lineales—específicamente mediante el uso de estas vallas ajustadas basadas en secantes—podemos hacer que los detectives "suficientemente buenos" sean mucho más inteligentes.

Han construido una herramienta que es de código abierto y se ejecuta sobre un motor existente (Z3), demostiendo que una estrategia más inteligente puede vencer a un enfoque de fuerza bruta en los tipos más difíciles de acertijos de enteros. Para cualquiera que intente verificar que una pieza de software no fallará o que un protocolo criptográfico es seguro, este nuevo método ofrece una forma más rápida y confiable de verificar las matemáticas que ocurren tras bambalinas.

En resumen, los autores tomaron un problema desordenado y curvo y dibujaron líneas más ajustadas alrededor de él, permitiendo que las computadoras encuentren la verdad mucho más rápido que antes.