Este extenso artículo de blog recorre la frontera entre los problemas computacionales resolubles y los que, por su complejidad intrínseca, solo admiten soluciones aproximadas. Tras una entrada anterior dedicada al cálculo de gradientes y la convexidad, el autor plantea la pregunta incómoda: ¿qué hacer cuando un problema se resiste a todos los trucos conocidos? La respuesta, sostiene, pasa por cuantificar exactamente su dificultad y aceptar métodos que intercambian certeza por velocidad.
El texto se apoya en el conjunto de datos de OpenFlights, formado por unos 7.700 aeropuertos y 67.000 rutas en aproximadamente 2 MB de CSV. A partir de ese material se construye un grafo con 3.425 nodos y 19.256 aristas, tras eliminar duplicados y auto-lazos. La distribución de grados muestra una cola pesada: el 21,9 % de los aeropuertos funcionan como hubs con al menos diez conexiones directas, mientras la inmensa mayoría enlaza con un puñado de destinos.
El autor desgrana después los fundamentos teóricos: la cuestión P contra NP, las reducciones polinómicas entre problemas, la NP-completitud de SAT y la del problema del viajante (TSP). Para ilustrarlo, resuelve un TSP concreto de doce aeropuertos con distancia media entre pares de 9.600 km, cuyo óptimo exacto queda fijado en 62.741 km. Luego compara ese resultado con métodos de Monte Carlo (2.000 tours aleatorios, media de 115.019 km, mejor tour a 75.277 km) y un algoritmo de quicksort aleatorio como ejemplo de algoritmo de Las Vegas. El propósito es mostrar que el hueco entre la solución exacta y las heurísticas no es un fracaso, sino la naturaleza misma de los problemas difíciles.