CAE TRAS 40 AÑOS EL LÍMITE DE VELOCIDAD PARA ENCONTRAR CLIQUES
Imaginemos una red social con n personas. ¿Hay un grupo de k de ellas que se conozcan todas entre sí? Los informáticos llaman a ese grupo un k-clique, y encontrar uno es un problema clásico con innumerables aplicaciones. El enfoque ingenuo comprueba cada grupo posible de k personas, aproximadamente n^k: una tarea imposible para redes grandes.
Un truco de 1985 y un largo desafío
Hace más de 40 años, Jaroslav Nešetřil y Svatopluk Poljak encontraron un atajo. Convirtieron la búsqueda de un k-clique en la búsqueda de un triángulo en un grafo más grande, lo que a su vez puede hacerse multiplicando matrices, grandes tablas de números. El coste depende de ω, el exponente de la multiplicación de matrices: su método requiere unos n^(ωk/3) pasos. Nadie conoce ω con exactitud. Vale al menos 2, y el artículo cita una cota superior reciente de 9/4.
El exponente de ese método de 1985 nunca se superó. En 2004, Gerhard Woeginger desafió a los investigadores a mejorarlo para algún k fijo; pasaron más de dos décadas. Mientras tanto, la hipótesis del k-clique (k-Clique Hypothesis), según la cual n^(ωk/3) es esencialmente lo mejor posible, se convirtió en un pilar de la «complejidad de grano fino» (fine-grained complexity). Los investigadores la usaron para argumentar que muchos otros problemas, desde el análisis sintáctico de gramáticas hasta el análisis de datos comprimidos, tampoco podían resolverse más rápido.
Un blanco móvil
Refutar esta hipótesis tenía una dificultad especial. Su coste previsto depende de ω, que se desconoce. Un algoritmo que superara el mejor valor actual de ω podría dejar de superar la hipótesis si alguien encontrara más adelante una multiplicación de matrices más rápida.
Virginia Vassilevska Williams, del MIT, y Or Zamir, de la Universidad de Tel Aviv, sortean el problema. Demuestran que, para todo k suficientemente grande, un k-clique puede encontrarse —e incluso contarse— en unos n^((ω/3 − c)k) pasos, donde c es una constante positiva que no depende ni de k ni de ω. El ahorro se mide respecto al verdadero valor de ω, sea cual sea. Se mantiene incluso si ω = 2, el mejor caso concebible.
Plegar una cuña
El núcleo del método se refiere a patrones de nueve vértices. El enfoque estándar los divide en tres grupos de tres y multiplica tres matrices enormes. Los autores se fijan en una cuña (wedge) —dos aristas que comparten un vértice— e insertan, entre dos de las matrices, una tabla que no cambia nada: la identidad. Luego escriben esa identidad como una suma de unos pocos «intercambios» (swaps), cada uno de los cuales fusiona las dos aristas de la cuña en una sola, más un resto de rango bajo.
Los intercambios dan patrones más simples con menos aristas, que se tratan de nuevo con el mismo método; un patrón de nueve vértices tiene como máximo 36 aristas, así que la recursión termina. El resto de rango bajo reduce las matrices que hay que multiplicar. Aplicar el truco a dos cuñas separadas a la vez es lo que conserva una ganancia incluso cuando ω = 2. Cualquier k múltiplo de nueve puede entonces agruparse en nueve bloques.
Real pero diminuta
Los autores no dan cifras para la ganancia. Describen las constantes como comprendidas «entre minúsculas sin optimización y diminutas con optimizaciones importantes». Lo importante no es la velocidad en la práctica: es que una barrera en la que se creyó durante décadas no existe.
Las consecuencias van más allá de los cliques. Los algoritmos exactos para problemas de optimización difíciles como Max-Cut y Max-2-SAT, que se ejecutaban en unos 2^(ωn/3) pasos para n variables, obtienen ahora también un exponente menor. Lo mismo ocurre con el recuento de copias de cualquier grafo pequeño fijo.
Lo que hizo la IA
En una sección específica, los autores describen cómo trabajaron con ChatGPT-6, utilizado a través de su interfaz web pública. Partiendo de sus propias ideas para cliques de cinco personas y de un resultado reciente de OpenAI que refuta otra conjetura, la hipótesis del tiempo exponencial (Exponential Time Hypothesis), el modelo encontró una primera mejora, complicada, para los 5-cliques. Después, los autores la destilaron, con ayuda de la IA, en la descomposición algebraica que constituye el núcleo de la demostración, y que consideran «casi puramente la contribución de la IA». El marco algorítmico construido a su alrededor es, según ellos, principalmente suyo.
Una observación destaca. Las demostraciones oscuras generadas por IA son difíciles de leer para los humanos, señalan los autores, y les «impresionó que también sean difíciles de entender para la propia IA».
