Por Canuto  

Un resultado de Nikhil Bansal y Haotian Jiang reduce de forma inédita la discrepancia en problemas de asignación y reaviva la posibilidad de demostrar una conjetura abierta desde los años 80.
***

  • El nuevo límite fija la discrepancia en la cuarta raíz del logaritmo del número de vectores, una mejora frente a la cota anterior.
  • La conjetura de János Komlós sostiene que el desequilibrio puede mantenerse por debajo de una constante universal, sin depender de la dimensión.
  • El método podría aportar herramientas para la optimización, la física y los sistemas de aprendizaje automático.

Dividir un grupo de personas en dos equipos parece sencillo hasta que cada integrante aporta habilidades distintas. Si una persona domina la historia, otra la música y una tercera las películas, repartirlas para que ambos bandos tengan capacidades similares se convierte en un problema matemático de alta dimensión. Esa clase de desafío, que también aparece al distribuir recursos, diseñar ensayos clínicos o asignar inventarios, acaba de recibir un importante avance tras casi 30 años.

Nikhil Bansal, informático de la Universidad de Michigan, y Haotian Jiang desarrollaron un método que mejora de manera importante la mejor cota conocida para la discrepancia. Su resultado no demuestra por completo la conjetura de Komlós, pero establece un límite que crece mucho más lentamente con el tamaño del problema. Investigadores externos describieron el trabajo como un avance importante y como una señal renovada de que la conjetura podría ser cierta.

El reto de repartir sin desequilibrios

La teoría combinatoria de la discrepancia estudia cómo dividir objetos en dos subconjuntos procurando que sus propiedades queden distribuidas de la manera más uniforme posible. Un ejemplo cotidiano sería formar dos equipos de trivia con niveles parecidos en varias categorías, aunque el mismo marco puede aplicarse a automóviles usados, participantes de un ensayo clínico o lotes de mercancía. La discrepancia mide cuánto se aleja la asignación de un reparto perfectamente equilibrado.

Los investigadores representan cada objeto como un vector unitario, una lista de coordenadas cuya longitud es uno y cuyos componentes reflejan atributos específicos. Si un vector se asigna a un equipo, conserva sus coordenadas; si se asigna al otro, sus coordenadas cambian de signo. Una distribución perfecta haría que todos los vectores se cancelaran y sumaran cero, aunque esa armonía rara vez se alcanza exactamente cuando aumentan los objetos y las características.

La conjetura formulada por János Komlós a comienzos de los años 80 plantea que, sin importar cuántos vectores o dimensiones tenga el problema, siempre existe una división cuya discrepancia no supera una constante universal. La idea resulta contraintuitiva porque muchos métodos naturales producen desequilibrios cada vez mayores conforme aumenta el número de objetos.

El aspecto sorprendente de la conjetura consiste precisamente en su independencia respecto de la dimensión. Una demostración tendría consecuencias para otros problemas de discrepancia y para áreas como la investigación de operaciones.

Un límite que se acerca a la constante

Las primeras estrategias ofrecían resultados que aumentaban con el tamaño del conjunto. En 1985, Joel Spencer obtuvo una cota superior relacionada con el logaritmo de N, mientras que posteriormente Wojciech Banaszczyk la redujo a la raíz cuadrada de ese logaritmo. Ambos resultados marcaron hitos, pero todavía dejaban una distancia considerable frente a la constante universal que anticipaba Komlós.

La participación de científicos de la computación cambió el modo de abordar el problema. En 2010, Bansal diseñó un algoritmo que comenzaba dividiendo cada vector por la mitad y luego desplazaba gradualmente esas fracciones hasta asignarlas por completo a uno de los dos equipos. El procedimiento controlaba la discrepancia en cada etapa y alcanzaba una cota del orden del logaritmo de N.

Más adelante, Bansal refinó el algoritmo hasta alcanzar una cota expresada como la raíz cuadrada del logaritmo de N. El avance mostró que los algoritmos podían producir soluciones concretas en un área donde muchos investigadores dudaban de que ese enfoque fuera posible.

El trabajo anunciado por Bansal y Jiang fija ahora la discrepancia en la cuarta raíz del logaritmo de N. Aunque esa expresión todavía depende del tamaño del problema, lo hace mucho más lentamente que las cotas anteriores. El resultado constituye la primera mejora importante sobre el problema de Komlós en décadas, pero no prueba todavía la conjetura completa.

La dependencia como nueva herramienta

Bansal y Jiang colaboraron en trabajos relacionados con algoritmos y discrepancia. Junto con otros colegas, demostraron una versión condicionada de la conjetura de Komlós. Esa experiencia los llevó a continuar trabajando para eliminar las condiciones restantes y buscar una mejora más profunda.

En febrero de 2025, Jiang visitó a Bansal durante una semana en Ann Arbor. Durante el segundo día, ambos tuvieron una intuición sobre cómo reducir la cota: en lugar de limitar únicamente la discrepancia acumulada, el algoritmo debía examinar cómo las perturbaciones en una propiedad afectaban a las demás. La idea partía de que las distintas dimensiones están entrelazadas, pero podían contener una forma de independencia aprovechable.

El nuevo procedimiento mide esa dependencia mientras divide los vectores en fracciones. Cuando una parte se modifica de forma aleatoria para convertirse en una asignación completa, el algoritmo intenta reducir simultáneamente los efectos sobre varias coordenadas. Esa coordinación ofrece un control más preciso del proceso y evita que corregir el desequilibrio en una dimensión provoque un problema mayor en otra.

El resultado fue la cota de la cuarta raíz del logaritmo de N, una mejora sustancial frente a la cota anterior. El trabajo refuerza la expectativa de que pueda existir una constante universal, aunque los autores y otros especialistas aún consideran que queda un obstáculo central por resolver.

Posibles aplicaciones y próximos obstáculos

La relevancia del resultado no se limita a una cuestión abstracta de matemáticas. La teoría de la discrepancia puede ayudar a estudiar problemas de optimización, investigación de operaciones y física, campos donde una distribución con pequeños desequilibrios puede simplificar decisiones complejas. La eficiencia del algoritmo también permite explorar nuevos problemas mediante métodos computacionales.

Las herramientas de discrepancia podrían tener relación con la organización de grandes cantidades de información y parámetros en sistemas de aprendizaje automático. Sin embargo, el resultado no constituye por sí mismo una aplicación concreta ya implementada en modelos de lenguaje o inteligencia artificial.

El nuevo límite también aporta información sobre la estructura que podría esconderse detrás de la conjetura de Komlós. La raíz cuadrada del logaritmo aparece con frecuencia en resultados matemáticos, pero la cuarta raíz es menos habitual, lo que sugiere que podría existir margen para avanzar más.

La estrategia algorítmica encuentra por ahora un límite en la cuarta raíz y superarlo requerirá una idea adicional. El resultado no cierra una pregunta abierta desde los años 80, pero cambia la percepción sobre su dificultad y ofrece una ruta concreta para seguir investigando.

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