ELEGIR NÚMEROS QUE SUMEN UN OBJETIVO, CASI TAN RÁPIDO COMO LEERLOS

He aquí un acertijo que cualquiera puede enunciar. Tienes una lista de números enteros —por ejemplo, 3, 9, 14, 20— y un objetivo, por ejemplo, 23. ¿Puedes elegir algunos de modo que sumen exactamente el objetivo? (Aquí, sí: 3 + 20 o 9 + 14.) Es la suma de subconjuntos (Subset Sum), uno de los problemas más fundamentales de la informática. El artículo lo describe como un problema NP-completo fundamental, una familia de problemas conocidos por ser difíciles de resolver con exactitud.

Pero hay un resquicio. Si los números no son demasiado grandes, algoritmos ingeniosos se ejecutan en un tiempo que depende de su tamaño. El método clásico, de Bellman en 1957, tarda un tiempo proporcional a la cantidad de números n multiplicada por el objetivo t. Desde entonces, los algoritmos no han dejado de mejorar:

• Pisinger (1999): proporcional a n × N, donde N es el número más grande;
• Bringmann (2017): aproximadamente n + t;
• varios equipos (2021–2024): aproximadamente n + N^(5/3), y después n + N^(3/2).

El santo grial era un tiempo de aproximadamente n + N, no mucho más que leer la entrada. Los investigadores del campo lo habían llamado «el problema abierto más crucial» de esta línea de trabajo.

A un pelo de la meta

Lin Chen, Yuchen Mao y Guochuan Zhang, de la Universidad de Zhejiang (China), presentan un algoritmo que se ejecuta en un tiempo n + N^(1+ε), donde ε puede ser cualquier número positivo pequeño fijado de antemano: 0,1, 0,01, 0,001. Es determinista, admite números negativos y valores repetidos, y viene acompañado de una demostración matemática. Los autores califican este tiempo de casi óptimo.

El resultado se extiende a vectores: elegir elementos de modo que varias sumas alcancen sus objetivos a la vez, con un tiempo N^(d+ε) para d coordenadas. Esto, a su vez, responde a parte de una pregunta planteada por varios grupos sobre la programación entera: encontrar soluciones con números enteros de sistemas de ecuaciones cuyas variables están acotadas. Se desarrollan explícitamente dos consecuencias: dividir un conjunto de números en dos mitades iguales y repartir tareas entre dos máquinas idénticas de la forma más equilibrada posible.

Elevar los números a una dimensión superior

La idea clave es geométrica. Ya se sabía que el problema es fácil cuando los números son densos y el objetivo está bien dentro del rango de sumas posibles. La observación de los autores: un conjunto disperso de números puede parecer denso visto en una dimensión superior.

Su ejemplo es el conjunto {11, 12, 22, 24}. Se escriben 11 y 22 como uno y dos pasos a lo largo de un primer eje, y 12 y 24 como uno y dos pasos a lo largo de un segundo eje. Las sumas posibles llenan entonces todos los puntos de un pequeño cuadrado de 4 por 4. Pero si se aplasta ese cuadrado de nuevo sobre una recta —calculando 11x + 12y—, las sumas forman siete grupos separados por huecos, dispersos entre 0 y 69. Los huecos son una ilusión de la proyección; en dos dimensiones, la estructura es sencilla.

El algoritmo construye esas coordenadas de dimensión superior para cualquier entrada, usando resultados de la combinatoria aditiva. Dentro de la región «llena», las respuestas salen gratis. Solo una delgada zona cerca del borde requiere trabajo de verdad, que el algoritmo divide en problemas más pequeños y resuelve de forma recursiva. Cada ronda reduce drásticamente esa zona, y solo se añade en total un número constante de dimensiones nuevas.

Cómo se construyó la demostración

El artículo comienza con un «aviso sobre IA». Los autores diseñaron ellos mismos la ruta principal de la demostración, basándose en sus propios trabajos recientes sobre versiones densas y multidimensionales del problema. Después usaron un modelo de IA, GPT Astra Ultra, para convertir esas ideas en demostraciones matemáticas completas. Se atascó en varios lemas, que se resolvieron con ideas de los autores; una nota de investigación pública documenta las conversaciones. Una vez terminado el algoritmo aleatorizado básico, el modelo lo extendió a las versiones deterministas y multidimensionales «sin ninguna orientación de los autores». El modelo también redactó el borrador del artículo y, según escriben los autores, verificó sus resultados principales con una demostración en el asistente de demostración Lean 4. Los autores asumen toda la responsabilidad del contenido.

Todavía no es la línea de meta

El exponente es 1 + ε y no exactamente 1, y las constantes ocultas crecen a medida que ε disminuye; la dependencia del número de dimensiones no está optimizada. Los propios autores describen el algoritmo como «bastante complejo». El artículo es teórico: no presenta ninguna implementación ni pruebas de rendimiento.