Teoría del todo

Parte V · Del electrón al programa

Algoritmos y complejidad

en cursoÚltima actualización: 23 de octubre de 2026 · Primera versión del capítulo

Se construye sobre: Qué se puede computar

Si te pido que busques la palabra “ornitorrinco” en un diccionario de papel, no empiezas por la primera página. Lo abres por la mitad, miras si te pasaste, descartas medio libro y repites. En unos cuantos gestos la tienes. Si las mismas palabras estuvieran desordenadas, en una lista sin criterio, no te quedaría otra que leerlas una por una.

Las dos maneras funcionan. Las dos terminan. Lo que las separa es el tiempo, y esa diferencia, que con un diccionario es de minutos, con millones de datos es la diferencia entre un programa útil y uno que nadie puede esperar. En qué se puede computar vimos la frontera de lo que ninguna máquina resuelve. Este capítulo se queda del lado posible y pregunta otra cosa: ¿cuánto cuesta?

Una receta que siempre termina

Un algoritmo es un procedimiento mecánico, en el sentido preciso de las máquinas de Turing, escrito para resolver un problema. Donald Knuth, al comienzo de The Art of Computer Programming, le pide cinco cosas: que termine después de un número finito de pasos, que cada paso esté definido sin ambigüedad, que tenga cero o más entradas, que produzca al menos una salida y que cada operación sea lo bastante básica como para hacerse con lápiz y papel. Una receta de cocina se parece, pero “sal al gusto” no pasaría el segundo requisito.

El ejemplo con que Knuth abre su libro tiene más de dos mil años: el algoritmo de Euclides, que aparece en el libro VII de los Elementos, para hallar el máximo común divisor de dos números. Divide el mayor entre el menor y quédate con el resto. Si el resto es cero, el menor es la respuesta. Si no, repite con el menor y el resto. Cuando leí ese primer volumen lo escribí en Python, así:

def euclides_algorithm(m, n):
    while (m % n) != 0:
        r = m % n
        m = n
        n = r
    return n

Con 1071 y 462: el resto de 1071 entre 462 es 147; el de 462 entre 147 es 21; el de 147 entre 21 es 0. El máximo común divisor es 21. El algoritmo descansa en una sola observación, que todo divisor común de y también divide al resto, y viceversa:

¿Y por qué termina? Porque los restos son números naturales que bajan estrictamente en cada vuelta, y una sucesión de naturales no puede bajar para siempre: tarde o temprano llega a cero. Es una propiedad de los números naturales la que garantiza que el ciclo while se acaba. Esta misma rutina, extendida para llevar la cuenta de los cocientes, es la que en anillos y cuerpos calcula el inverso que hace funcionar a RSA.

Contar pasos, no segundos

Medir un algoritmo con cronómetro sirve de poco: el mismo programa tarda distinto en un portátil viejo y en un servidor, y cada paso abstracto se vuelve un puñado de instrucciones del procesador que cuento en del sumador a la CPU. Lo que no depende de la máquina es cómo crece el número de pasos cuando crece el tamaño de la entrada. Para eso está la notación O grande. Si y son funciones de los naturales en los reales no negativos,

Dice que, a partir de cierto tamaño, no crece más rápido que , salvo por una constante. Las constantes se ignoran a propósito: son las que cambian de un computador a otro. La forma de la función que cuenta los pasos, en cambio, es del algoritmo.

El diccionario es el ejemplo perfecto. Buscar en una lista desordenada de elementos exige, en el peor caso, mirarlos todos: . Buscar en una lista ordenada partiéndola por la mitad cada vez, la búsqueda binaria, exige en el peor caso comparaciones: . Con un millón de nombres, la primera puede necesitar un millón de miradas; la segunda, veinte. Es el juego de adivinar un número con preguntas de sí o no de entropía e información: cada pregunta bien hecha vale un bit, y un millón de opciones caben en veinte bits.

Euclides también es rápido. Un teorema de Gabriel Lamé, del siglo XIX, dice que el número de divisiones nunca pasa de cinco veces el número de cifras decimales del menor de los dos números. El peor caso son dos números de Fibonacci consecutivos, y aun así el trabajo crece como el número de cifras, no como el tamaño de los números.

Ordenar

La búsqueda binaria necesita la lista ordenada, así que la pregunta siguiente es cuánto cuesta ordenar. La manera más natural, la que se usa para ordenar cartas en la mano (tomar una y meterla en su sitio entre las ya ordenadas), hace en el peor caso comparaciones: . Hay métodos mejores. El de mezcla parte la lista en dos, ordena cada mitad y las intercala; hace comparaciones. Con mil elementos la diferencia ya es grande: cerca de medio millón de comparaciones contra unas diez mil.

Y se puede probar que no hay nada esencialmente mejor, si lo único que el algoritmo puede hacer es comparar pares. Hay órdenes posibles de la lista y cada comparación es una pregunta de sí o no, así que en el peor caso hacen falta al menos

comparaciones. Es otra vez un argumento de información: para elegir uno entre casos necesitas esos bits, y no hay truco que los ahorre.

El camino más corto

Un problema que se ve en cualquier aplicación de mapas: dadas unas ciudades y las carreteras entre ellas, cada una con su longitud, ¿cuál es la ruta más corta desde aquí a todas las demás? Es una pregunta sobre un grafo, puntos unidos por líneas con pesos, y la respuesta clásica la publicó Edsger Dijkstra en 1959. Es de esos algoritmos que uno anota y vuelve a mirar, porque cabe en un párrafo.

Retrato de Edsger Dijkstra, un hombre mayor de barba canosa y gafas de marco delgado, con camisa a cuadros y chaleco de lana rojizo, mirando hacia un lado
Edsger Dijkstra, fotografiado por su colega Hamilton Richards en sus últimos años. Contaba que el algoritmo del camino más corto lo pensó en unos veinte minutos, sentado en un café de Ámsterdam, sin lápiz ni papel.Foto: Hamilton Richards · CC BY-SA 3.0 · Wikimedia Commons

Lleva una distancia provisional para cada ciudad: 0 para el origen, infinito para las demás. En cada paso, toma la ciudad no fijada con la menor distancia provisional y fíjala: esa ya es definitiva. Luego mira sus vecinas y, si llegar a alguna pasando por la recién fijada es más corto que lo que tenías, actualiza. Repite hasta fijarlas todas.

Juega · Dijkstra en el Eje Cafetero

Las ciudades son reales; las distancias son de juguete, inventadas para el ejemplo. Avanza paso a paso desde Pereira y, cuando quieras, elige un destino para ver su mejor ruta conocida hasta ese momento.

5121820223040254530Pereira · 0Dosquebradas · ∞Santa Rosa · ∞Chinchiná · ∞Manizales · ∞Cartago · ∞Armenia · ∞
se fija ahoradistancia definitivamejor llegada conocida
destino
paso 0 de 7

Al empezar solo sabemos que Pereira está a 0 de sí misma; todas las demás están a ∞ (todavía no sabemos llegar).

En el mapa de juguete (las ciudades existen; las distancias me las inventé para que el ejemplo enseñe algo) se ven los dos momentos del algoritmo. A Santa Rosa hay carretera directa de 18, pero al fijar Dosquebradas, a 5, aparece un camino de 5 + 12 = 17 y la distancia provisional baja. A Manizales se llega primero por Santa Rosa, con 57, y luego por Chinchiná, con 30 + 22 = 52. El orden en que se fijan las ciudades es el orden de sus distancias: Pereira, Dosquebradas, Santa Rosa, Cartago, Chinchiná, Armenia, Manizales.

¿Por qué se puede fijar una ciudad sin miedo a equivocarse? Si la ciudad tiene la menor distancia provisional entre las no fijadas, cualquier otra ruta hasta ella tendría que salir de la zona ya fijada por alguna ciudad no fijada, que está a o más, y lo que falte del camino no puede restar. Esa última frase es una hipótesis, no un detalle: el algoritmo funciona solo si ninguna longitud es negativa. Con longitudes negativas (que en un mapa no existen, pero en otros grafos sí, por ejemplo cuando los pesos son costos que pueden ser ganancias) hay que usar otros métodos.

La versión de la animación, que en cada paso revisa todas las ciudades para encontrar la más cercana, hace del orden de operaciones con ciudades. Con una estructura de datos llamada montículo baja a , donde es el número de carreteras. En cualquier caso es un polinomio: aunque el mapa sea de un país, el problema es manejable. Las vías reales, con sus curvas y pendientes, son las de puentes y carreteras; aquí cada vía es solo un número.

P contra NP

Cambia la pregunta un poquito. Ya no quiero ir de Pereira a todas partes; quiero salir de Pereira, pasar por cada ciudad exactamente una vez y volver, recorriendo lo menos posible. Es el problema del viajero. Parece un primo cercano del anterior y, sin embargo, nadie conoce un algoritmo eficiente para resolverlo.

Probar todas las rutas no sirve. Con ciudades hay

recorridos distintos (fijas dónde empiezas y no importa el sentido). Con las siete del mapa son 360, nada. Con 20 son unos : revisando mil millones por segundo tardarías casi dos años. Con 25, casi diez millones de años. Hay métodos mucho más astutos que la fuerza bruta, y en la práctica se resuelven casos enormes o se encuentran rutas casi óptimas. Lo que nadie tiene es un método que garantice la ruta óptima en tiempo polinomial para todos los casos.

Para hablar de esto con precisión se usan preguntas de sí o no. La clase P reúne los problemas que algún algoritmo resuelve en tiempo , para algún fijo, siendo el tamaño de la entrada. La clase NP reúne los problemas en los que, cuando la respuesta es sí, existe una prueba corta que se puede verificar en tiempo polinomial. “¿Hay un recorrido de longitud menor que 300?” está en NP: si alguien te muestra el recorrido, sumas y compruebas. Encontrarlo es otra historia. Todo problema de P está en NP, porque si sabes resolverlo rápido, sabes verificarlo rápido. La pregunta es si vale lo contrario:

¿Todo lo que se verifica rápido se puede también resolver rápido? Nadie lo sabe. Es uno de los problemas del milenio del Instituto Clay, con un millón de dólares para quien lo resuelva. En encuestas entre especialistas la gran mayoría apuesta a que , pero una apuesta no es una demostración, y las técnicas conocidas ni siquiera parecen estar cerca.

Lo que sí se sabe es asombroso. A comienzos de los años setenta, Stephen Cook, y de forma independiente Leonid Levin, demostraron que hay problemas en NP que son los más difíciles de todos, los NP-completos: cualquier problema de NP se puede traducir a ellos en tiempo polinomial. El primero es SAT: dada una fórmula lógica, ¿hay una manera de asignar verdadero o falso a sus variables que la haga verdadera? Dicho en el idioma de lógica y compuertas: dado un circuito, ¿hay alguna entrada que encienda la salida? Poco después Richard Karp mostró una lista larga de problemas NP-completos, y hoy son miles: la versión de sí o no del viajero, colorear mapas con tres colores, el sudoku generalizado a tableros de cualquier tamaño. Si uno solo de ellos tuviera un algoritmo polinomial, todos lo tendrían, y P sería igual a NP.

Por qué importa más allá de la teoría

La criptografía vive de esta brecha. RSA, como cuento en anillos y cuerpos, es seguro mientras factorizar números grandes sea difícil. Factorizar está en NP (si alguien te da un factor, lo compruebas dividiendo), así que si P fuera igual a NP con un algoritmo práctico, RSA caería. El revés no alcanza: aunque P sea distinto de NP, eso no prueba que factorizar sea difícil, porque no se cree que factorizar sea NP-completo. La seguridad de casi todo lo que viaja cifrado por internet descansa en conjeturas, no en teoremas.

Y hay contrastes que sorprenden. Decidir si un número es primo, sin pedir sus factores, sí está en P: lo demostraron Agrawal, Kayal y Saxena en 2002. En la práctica se usa algo todavía más rápido, la prueba de Miller–Rabin, que lanza bases al azar: si el número es compuesto, cada ronda lo delata con probabilidad de al menos tres cuartos, así que tras rondas la probabilidad de equivocarse es a lo sumo . Es un algoritmo que usa la probabilidad como herramienta y acepta un error tan pequeño como uno quiera.

La complejidad aparece también en la inteligencia artificial. Para algunas redes neuronales muy pequeñas ya está demostrado que encontrar los pesos óptimos es NP-difícil, y por eso entrenar no busca el óptimo: baja la montaña hasta un valle que sirva. Y un sistema como el de una IA que cita la ley busca, entre los fragmentos, los más parecidos a una pregunta; con un pliego, compararlos todos es barato, pero con millones de fragmentos esa búsqueda lineal pesa, y por eso a esa escala se usan índices aproximados que cambian un poco de exactitud por mucha velocidad. Es la misma negociación de siempre: no basta con que un problema se pueda resolver. Tiene que poder resolverse antes de que deje de importar.