MEZCLAR MENSAJES SUPERA A ENCAMINARLOS, TRAS 22 AÑOS DE DUDA

Imagine una red de cables en la que varios emisores quieren llegar cada uno a su propio receptor. El enfoque clásico es el encaminamiento (routing): cada mensaje viaja como un paquete por uno o varios caminos, y el tráfico puede incluso repartirse entre muchos caminos en cualquier proporción. La codificación de red (network coding) añade una libertad más: los nodos intermedios pueden combinar los mensajes que reciben —por ejemplo, sumándolos— en lugar de limitarse a reenviarlos.

La pregunta es si esa libertad permite alguna vez que pasen más datos. El artículo se centra en las redes no dirigidas, en las que un cable puede transportar datos en cualquiera de los dos sentidos, pero ambos sentidos comparten una única capacidad.

Una conjetura confirmada caso tras caso

En 2004, Li y Li conjeturaron que, en este contexto, la codificación no aporta ninguna ventaja frente al encaminamiento fraccionario; Harvey, Kleinberg y Rasala Lehman formularon la misma conjetura de forma independiente. Durante las dos décadas siguientes se confirmó para una clase de redes tras otra —dos sesiones, ciertas redes planas, redes con como máximo seis nodos de codificación, y más—, pero nunca se resolvió en general. Otros resultados de la teoría de la complejidad, como cotas inferiores para ordenar enteros en memoria externa y para circuitos de multiplicación, se habían demostrado incluso suponiéndola cierta.

La teoría conocida ya limitaba lo que estaba en juego: la codificación puede superar al encaminamiento como mucho en un factor logarítmico. Y un resultado de 2017 de Braverman, Garg y Schvartzman mostró que una sola red con una ventaja estricta de la codificación podía amplificarse hasta una brecha mucho mayor. Todo se reducía a encontrar un ejemplo finito.

Basta con sumar

El apéndice ofrece el artilugio básico, que muestra por qué mezclar puede ayudar. Se colocan varias fuentes alrededor de un nodo central v, sus receptores alrededor de otro nodo central w, y se unen v y w con un cable. Cada fuente tiene además pequeños caminos laterales hacia los otros receptores. En tres rondas, el cable central transporta la suma de todos los mensajes; cada receptor recibe esa suma más los otros mensajes por los caminos laterales, y recupera el suyo por resta. Sin el cable central, cada fuente está a cinco saltos de su receptor.

Ese artilugio, procedente de trabajos anteriores de Haeupler, Wajc y Zuzic, hace que la codificación sea más rápida, pero no le permite por sí solo transportar más: un camino largo puede seguir funcionando como una tubería de alto caudal.

Un circuito convertido en red

Xindan Zhang y Baochun Li, de la Universidad de Toronto, y Zongpeng Li, de la Universidad Tsinghua, encontraron el paso que faltaba. Convierten un código corto en un cálculo reversible: un circuito de sumas enteras invertibles que calcula, copia el resultado y luego deshace su trabajo intermedio. Después construyen una red nueva cuyos cables físicos son los hilos de ese circuito, y asignan a cada registro del cálculo, incluidos los registros auxiliares, su propia demanda emisor-receptor.

Una contabilidad minuciosa del «tiempo» a lo largo de los hilos hace el resto. Sumadas sobre todos los hilos, las longitudes coinciden exactamente con las distancias mínimas que deben cubrir las demandas. Pero las demandas designadas no pueden evitar ciertas puertas que cuestan dos unidades adicionales. Así que el encaminamiento se queda estrictamente por debajo del caudal completo, mientras que el código usa cada cable exactamente una vez y, encadenado sobre muchos bloques, se acerca a un caudal de uno.

Qué se demuestra

• Una red conexa finita, con cada nodo unido como máximo a otros tres y capacidad unitaria en cada cable, en la que un sencillo código lineal binario supera al mejor encaminamiento fraccionario posible. La conjetura de 2004 es falsa.
• La misma construcción entera funciona a la vez sobre todo cuerpo finito y todo grupo abeliano finito no trivial.
• Combinando copias repetidamente, los autores construyen familias infinitas de redes en las que la codificación se acerca al caudal completo mientras el encaminamiento cae como una potencia de 1/log n: una ventaja polilogarítmica.

El artículo no indica el número de nodos de su contraejemplo. Solo su bloque básico es ya un código que dura 13.122 rondas.

Verificado por máquina

Tanto el contraejemplo finito como el teorema de las familias están formalizados en el asistente de demostración Lean. Según los autores, una auditoría de 2.472 declaraciones y 1.755 teoremas muestra que las demostraciones usan solo los tres axiomas estándar de Lean, sin demostraciones incompletas; una nueva verificación independiente en un entorno limpio también tuvo éxito, aunque con el mismo núcleo de Lean.

Qué queda abierto

Los autores enumeran tres preguntas: el tamaño real de la ventaja en su ejemplo finito, si el techo logarítmico conocido se alcanza realmente y si existe un contraejemplo pequeño. Su última frase resume la situación: «Resulta que la codificación sí ayuda en las redes no dirigidas; cuánto puede ayudar está por ver».

Uso de IA declarado. Una nota a pie de página indica que GPT-6 Astra, de OpenAI, ayudó a desarrollar las demostraciones y el código en Lean.