El trabajo del investigador de IMDEA Software Alessio Mansutti, Dmitry Chistikov y Mikhail Starchak «Integer Linear-Exponential Programming in NP by Quantifier Elimination», , ganó el premio al mejor trabajo en el International Colloquium on Automata, Languages, and Programming (ICALP) Track B 2024, que es una reunión de investigación emblemática.
¿Se pueden dar $15$ euros a alguien utilizando menos billetes de $5$ euros que monedas de 2 euros? Los informáticos y los matemáticos pueden ver este problema como la tarea de encontrar una solución al sistema de ecuaciones
$5x + 2y = 15$
$x < y$
$x ≥ 0$
$y ≥ 0$
donde x e y son variables que representan la cantidad de billetes de $5$ euros y de monedas de $2$ euros a utilizar. Las restricciones $x ≥ 0 e y ≥ 0$ especifican que esta cantidad no puede ser negativa, mientras que las restricciones $5x+2y = 15 y x < y$ codifican nuestro problema de alcanzar exactamente $15$ euros utilizando menos billetes que monedas. No está permitido por la mitad: ¡$x$ e $y$ deben ser números enteros!
El problema anterior (que, por cierto, tiene solución: $x = 1 e y = 5$) es un ejemplo de un problema más general llamado Programación Lineal Entera (PLI). Este problema pregunta si es posible asignar valores enteros a un conjunto de variables $x_1, \dots, x_d$ de forma que se satisfaga un sistema de varias ecuaciones de la forma
$a_1 \cdot x_1 + \dots + a_d \cdot x_d ≤ c$,
donde $a_1, \dots, a_d$ y $c$ son constantes enteras (por ejemplo, arriba, $2$ y $15$ son algunas de estas constantes).
Los ILP son un problema fundamental en informática y, tras muchas décadas de investigación e ingeniería, ahora disponemos de software eficiente para resolverlo.
¿Encontrar la mejor ruta para que un conductor traiga un paquete a tu dirección? Eso está resuelto con ILP. ¿Programar aviones, sus rutas y sus tripulantes? Las aerolíneas utilizan el ILP no sólo para estas tareas, sino también para optimizar el precio de los billetes. ¿Cómo cuantifican los bancos el riesgo de prestar dinero a un prestatario? Utilizan solucionadores ILP. ¿Cómo se distribuyen las frecuencias disponibles en las redes móviles GSM entre las antenas para minimizar las interferencias? ¡ILP! Siempre que las empresas necesitan resolver un problema de planificación difícil, recurren a ILP.
Hay problemas que no pueden resolver con ILP. Tomemos por ejemplo el siguiente programa
Input: an integer $y ≥ 1$
Output: an integer $x$
$x ← 1$
while $y > 0$ do
$y ← y − 1$
$x ← 2 \cdot x$
end while
return $x$
Este programa toma como entrada un entero positivo y, y repetidamente le resta 1 hasta que se convierte en cero. Cada vez que se realiza una resta, una variable $x$, que inicialmente es $1$, se multiplica por $2$. Una vez que y se hace cero, el programa devuelve el valor actual de $x$. Podemos pedir un sistema de restricciones que caracterice los posibles valores que toma x al final del programa, para las distintas opciones de la entrada y. Para $y = 1$, $x$ is $2$. Para $y = 2$, $x$ is $4$. $y = 3$, $x$ is $8$, y así sucesivamente. En general obtenemos el sistema de restricciones
$y ≥ 1$
$x = 2^y$
donde $2^y$ es la función exponencial: $2$ multiplicado a sí mismo y veces.
Muchas técnicas para demostrar que los programas no contienen bugs requieren de restricciones como el anterior y comprobar si el sistema resultante tiene solución. Sin embargo, nos enfrentamos a un problema importante: la función exponencial no puede expresarse en ILP. ¿Cómo podemos comprobar entonces si el tiene solución? ¿Es posible comprobarlo?
Lo anterior es un ejemplo del problema de programación lineal exponencial entera ¿es posible asignar valores enteros a las variables $x_1, \dots, x_d$ de forma que se satisfaga un sistema de ecuaciones de la forma
$a_1 \cdot x_1 + \dots + a_d \cdot x_d + b_1 \cdot 2^{x_1} + \dots + b_d \cdot 2^{x_d} ≤ c$,
donde $a_1, \dots , a_d$, $b_1, \dots , b_d$ y $c$ son constantes enteras? El trabajo de Alessio, Dmitry y Mikhail muestra no sólo que existe un algoritmo para resolver este problema, sino también que se puede hacer (de momento, en teoría) ¡tan rápido como resolver ILP! Más concretamente, su trabajo muestra que la Programación Lineal-Exponencial Entera pertenece a NP, la clase de complejidad que se encuentra en el centro del famoso dilema P vs. NP. Se trata de una noticia apasionante, ya que puede allanar el camino para ampliar los solucionadores de ILP a problemas que requieran la función exponencial, como los derivados de la verificación de programas.
¿Quiere saber más? ¡Consulta el artículo!
El Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP) es el congreso más importante y la reunión anual de la European Europea de Informática Teórica (EATCS). La conferencia se en 1972, y este año celebraba su 51ª edición. Se celebró en Tallin, Estonia, del 8 al 12 de julio de 2024.
