Informática e IAPrepublicaciónTeoría3 min de lectura

ORDENAR CON COMPARACIONES PROHIBIDAS, CASI IGUAL DE RÁPIDO

Para poner n elementos en orden comparándolos de dos en dos, unas n log n comparaciones son a la vez necesarias y suficientes. Pero eso supone que dos elementos cualesquiera pueden compararse.

A menudo no es posible. Los autores toman prestado un ejemplo de un artículo de 2011: varios candidatos optan al mismo empleo, cada uno con sus referencias. Dos candidatos solo pueden compararse si alguna referencia conoce a ambos. Las comparaciones permitidas forman una red, un grafo: cada elemento es un punto, cada comparación permitida un enlace. El orden verdadero está oculto, pero se garantiza que el grafo lo contiene, como un camino que une cada elemento con el siguiente. La pregunta: ¿cuántas comparaciones hacen falta para recuperar el orden? Es la ordenación generalizada (generalized sorting).

Por qué fallan los trucos habituales

Los algoritmos clásicos se basan en la libertad de elección. QuickSort elige un «pivote» y lo compara con la mayoría de los demás elementos, pero un grafo arbitrario puede no tener ningún elemento unido a la mayoría de los demás. MergeSort divide los elementos en grupos y ordena cada uno, pero puede que un grupo no se pueda ordenar por sí solo: dos elementos que son vecinos en el orden final no tienen por qué estar unidos dentro de él. Más en el fondo, la ordenación corriente siempre dispone de una comparación que descarta una buena parte de los órdenes posibles; con comparaciones restringidas, puede que no haya ninguna.

Los avances fueron lentos. En 2011, Zhiyi Huang, Sampath Kannan y Sanjeev Khanna encontraron un método que usaba unas n¹·⁵ comparaciones, salvo factores logarítmicos, y esa cota se mantuvo desde entonces para grafos arbitrarios. Llegaron a preguntarse si el problema podría ser fundamentalmente más difícil que la ordenación corriente y necesitar n elevado a una potencia mayor que 1.

Predecir primero, reparar después

Sanjeev Khanna, de la Universidad de Nueva York, Aaron Putterman, de la Universidad de Harvard, y Junkai Song, también de la Universidad de Nueva York, responden ahora a esa pregunta: no. Su algoritmo aleatorizado ordena con unas n log⁴ n comparaciones de media, en cualquier grafo: solo unos pocos factores logarítmicos por encima de la ordenación corriente. Y, escriben, es «relativamente sencillo». Pero la ganancia es teórica: las constantes de la demostración son enormes (factores como 2³²), así que la ventaja solo se nota para n muy grandes.

Se apoya en un resultado conocido: si alguien te entrega una conjetura sobre la dirección de cada enlace, errónea en w de ellos, el orden puede recuperarse con unas n log n + w comparaciones. Así, la tarea pasa a ser producir una conjetura con pocos errores usando pocas comparaciones. Los pasos clave:

  • Una primera conjetura aproximada. Comparar una muestra aleatoria de parejas unidas y elegir cualquier orden compatible con las respuestas. Comete muchos errores, pero no demasiados.
  • Aislar los errores en lugar de corregirlos. En vez de corregir las conjeturas erróneas, el algoritmo localiza partes del grafo donde los errores son más densos que la media y las aparta. Cada ronda reduce los errores restantes, en promedio, en un factor de cuatro.
  • Volver más tarde. Los enlaces apartados se tratan en una fase posterior. Cada fase resuelve al menos la mitad de los enlaces aún pendientes, así que unas veinte fases bastan para un millón de enlaces.

Una demostración hallada con máquinas

La declaración sobre IA del artículo es inusualmente detallada. Afirma que ChatGPT 6-Astra «fue esencial para demostrar las cotas mejoradas». Un modelo encontró primero un algoritmo que usaba unas n¹·³³ comparaciones y luego se estancó. Los autores lo llevaron hasta n¹·²; después, tras decenas de instrucciones a lo largo de varias semanas, los modelos encontraron mejoras sucesivas —n^(10/9), n^(17/16), n^(19/18)— antes de llegar al algoritmo casi lineal. Los autores añaden que no está claro si su propio paso intermedio fue esencial para ese descubrimiento final.

Lo que sigue abierto

El resultado cuenta comparaciones, no tiempo de cálculo: tal como está planteado, el algoritmo no se ejecuta en tiempo polinómico, mientras que el método de 2011 sí lo hacía. Los autores enumeran tres preguntas abiertas: si pueden eliminarse los factores logarítmicos restantes, si un algoritmo sin aleatoriedad puede lograr lo mismo y si un algoritmo eficiente puede alcanzar el mismo número de comparaciones, o siquiera superar n¹·⁵.