Por Canuto  

Un algoritmo desarrollado por Nikhil Bansal y Haotian Jiang redujo de forma inédita el desequilibrio posible entre grupos, un resultado que fortalece la conjetura de Komlós y podría tener aplicaciones en optimización, finanzas y aprendizaje automático.
***

  • El nuevo límite para la discrepancia baja hasta la cuarta raíz de log(N), la primera mejora importante en casi tres décadas.
  • La conjetura de Komlós plantea que el desequilibrio puede mantenerse por debajo de una constante universal, sin importar la dimensión del problema.
  • El algoritmo eficiente podría impulsar avances en teoría de la optimización, física, finanzas y modelos de lenguaje, aunque esas aplicaciones aún son potenciales.

Un problema matemático que parece tan cotidiano como formar dos equipos equilibrados acaba de recibir su avance más importante en casi 30 años. Nikhil Bansal, de la Universidad de Michigan, y Haotian Jiang, de la Universidad de Chicago, desarrollaron un algoritmo que reduce de manera inédita el desequilibrio posible al distribuir objetos con múltiples características.

El resultado no demuestra todavía la conjetura de Komlós, una de las preguntas consideradas más difíciles de la teoría combinatoria de la discrepancia, pero cambia las expectativas sobre su posible solución. Según explicó Quanta Magazine, el nuevo límite crece tan lentamente con el número de objetos que, incluso en problemas con una cantidad astronómica de dimensiones, se mantiene muy cerca de una constante universal.

El desafío de repartir atributos sin perder el equilibrio

La teoría de la discrepancia estudia cómo dividir un conjunto de objetos en dos grupos procurando que ambos reciban cantidades similares de cada atributo relevante. El ejemplo intuitivo es un equipo de trivia: si una persona domina la historia, otra las películas y una tercera el básquetbol universitario, repartirlas de manera justa exige equilibrar muchas capacidades al mismo tiempo, no solo el número de integrantes.

En términos matemáticos, cada objeto puede representarse como un vector unitario, es decir, una flecha de longitud 1 cuyas coordenadas indican cuánto posee de cada característica. Al asignarlo a un grupo, sus coordenadas conservan el signo original; al colocarlo en el otro, todas se multiplican por menos 1, de modo que el problema consiste en elegir orientaciones que hagan que la suma total se acerque lo más posible a cero.

Una división perfecta significaría que los dos grupos tendrían exactamente el mismo balance en todas las dimensiones consideradas. Sin embargo, la igualdad absoluta suele ser imposible, por lo que los investigadores miden qué tan lejos queda la suma del punto de equilibrio y llaman discrepancia a esa distancia, una magnitud que resume el desbalance acumulado.

La conjetura formulada por János Komlós a comienzos de la década de 1980 sostiene que siempre debería existir una división cuya discrepancia permanezca por debajo de una misma constante, sin importar cuántos vectores u atributos tenga el problema. Haotian Jiang calificó esa idea de asombrosa porque propone una constante universal que no depende de la dimensión, mientras Nikhil Bansal la describió como uno de los problemas del santo grial de esta rama matemática.

De los límites crecientes a la cuarta raíz

La conjetura parecía difícil de aceptar porque las estrategias más sencillas producen un desequilibrio cada vez mayor a medida que aumenta el número de vectores, identificado como N. Asignar cada objeto al azar puede generar una discrepancia que crece de forma importante, una señal de que la intuición cotidiana sobre el equilibrio no basta cuando se multiplican las dimensiones.

Los investigadores lograron reducir progresivamente ese crecimiento, aunque sin alcanzar la constante propuesta por Komlós. En 1985, Joel Spencer estableció un límite proporcional al logaritmo de N, y en 1998 Wojciech Banaszczyk lo mejoró hasta la raíz cuadrada de log(N), un récord que permaneció vigente durante décadas, pero que todavía aumentaba indefinidamente.

El trabajo de Bansal y Jiang establece ahora un límite de la cuarta raíz de log(N), una mejora que puede parecer modesta en su notación, pero que resulta enorme en la práctica. Daniel Spielman, de la Universidad de Yale, señaló que durante la vida cotidiana no aparecerá un valor de N para el cual esa cuarta raíz supere 5, por lo que el comportamiento se acerca considerablemente al de una constante.

Aleksandar Nikolov, científico informático de la Universidad de Toronto, afirmó que antes se inclinaba a pensar que el límite conocido podía ser el correcto y que solo faltaba demostrarlo. El nuevo resultado lo sorprendió y lo dejó mucho más convencido de que la conjetura de Komlós probablemente sea verdadera, aunque todavía queda por eliminar el crecimiento residual asociado con log(N).

Un algoritmo para controlar dependencias ocultas

La estrategia de Bansal comenzó a tomar forma en 2010, cuando propuso dividir cada vector en mitades y distribuir gradualmente esas fracciones hasta que cada objeto quedara por completo en uno de los dos grupos. El procedimiento usaba pasos aleatorios cuidadosamente controlados para impedir que la discrepancia aumentara demasiado durante el proceso, una idea que permitió igualar primero el límite de Spencer.

En 2016, Bansal ajustó el método para alcanzar el límite de Banaszczyk y mostró que una computadora podría ejecutar de manera eficiente ese tipo de división. Raghu Meka, investigador de la Universidad de California en Los Ángeles, describió aquella posibilidad como algo completamente fuera de lo común, porque muchos especialistas pensaban que no podía existir un algoritmo capaz de encontrar soluciones con garantías tan fuertes.

Bansal conoció a Jiang en 2019, cuando ambos coincidieron en una conferencia y descubrieron intereses comunes en los algoritmos de discrepancia. Después de demostrar la conjetura de Komlós bajo condiciones específicas junto con Meka y otros dos investigadores, decidieron concentrarse en la versión general; Bansal atribuyó parte del progreso a la química entre ambos y a su capacidad para desarrollar ideas todavía incompletas en colaboración.

La pista decisiva apareció durante una visita de Jiang a Ann Arbor en febrero de 2025. En lugar de controlar únicamente la discrepancia total, los investigadores añadieron una medida de dependencia para estimar cuánto cambiaría un atributo cuando otro fuera perturbado al azar, y diseñaron la conversión de fracciones en valores enteros para reducir los efectos conjuntos entre dimensiones.

Qué puede significar el avance

El punto central del método es que los atributos pueden estar profundamente entrelazados sin que todos sus efectos deban interferir de manera inevitable. Al encontrar movimientos que mantienen bajo control la interacción entre dimensiones, el algoritmo permite conducir el sistema hacia una asignación equilibrada con más precisión que los procedimientos anteriores, aunque no elimina por completo la discrepancia.

Rainie Heck, del Instituto de Matemáticas Alfréd Rényi en Hungría, destacó que el algoritmo es eficiente, una característica especialmente relevante para sus posibles usos posteriores. Esa eficiencia permitiría aplicar la técnica a otros problemas abiertos de la teoría de la discrepancia y a preguntas de optimización en las que repartir recursos, datos o decisiones con restricciones simultáneas resulta esencial.

Las aplicaciones potenciales abarcan campos como la física, las finanzas y la investigación de operaciones, aunque el resultado no constituye por sí mismo una herramienta comercial ni una solución inmediata para esos sectores. Heck también estudia cómo la teoría de la discrepancia puede ayudar a mejorar modelos de lenguaje grandes y otros sistemas de aprendizaje automático, áreas donde distribuir información y limitar sesgos entre múltiples dimensiones representa un desafío constante.

La conjetura sigue sin resolverse y Bansal duda de que la estrategia algorítmica utilizada desde 2010 pueda completar el trabajo. El investigador afirmó que el equipo encontró un muro en la cuarta raíz y que superarlo requerirá algo completamente nuevo, mientras Spielman considera improbable que una cuarta raíz sea la respuesta final porque ese tipo de comportamiento rara vez aparece como solución definitiva en problemas matemáticos.

Por ahora, el avance ofrece la evidencia más convincente de que la propuesta de Komlós quizá no era tan irresponsable como su propio autor bromeó al recordarla. La posibilidad de que exista una constante universal para equilibrar sistemas de complejidad extrema mantiene abierta una pregunta con consecuencias que podrían extenderse desde las matemáticas puras hasta los algoritmos que organizan decisiones en el mundo real.

Imagen original de DiarioBitcoin, creada con inteligencia artificial, de uso libre, licenciada bajo Dominio Público.

Este artículo fue escrito por un redactor de contenido de IA y revisado por un editor humano para garantizar calidad y precisión.


ADVERTENCIA: DiarioBitcoin ofrece contenido informativo y educativo sobre diversos temas, incluyendo criptomonedas, IA, tecnología y regulaciones. No brindamos asesoramiento financiero. Las inversiones en criptoactivos son de alto riesgo y pueden no ser adecuadas para todos. Investigue, consulte a un experto y verifique la legislación aplicable antes de invertir. Podría perder todo su capital.

Suscríbete a nuestro boletín

Artículos Relacionados