Po stopách obchodního cestujícího – Cook William (2012)

Imagina que tienes una lista de ciudades que necesitas visitar, cada una una vez, y al final de tu viaje, quieres volver a casa. ¿Cómo encuentras la ruta más corta? Esta es la esencia del problema del vendedor viajero. Es muy simple, y la solución seguramente también lo es: solo probamos todas las rutas y elegimos la más corta. Pero hay un inconveniente: incluso con 85 ciudades, hay más rutas que átomos en el universo visible. Eso probablemente es inmanejable. Encontrar la conexión más corta entre muchos puntos se utiliza en una variedad de campos, desde la fabricación de microchips hasta la planificación del movimiento del telescopio Hubble, y al emplear métodos de búsqueda avanzados, se ahorran decenas de miles de millones de dólares anualmente. Sin embargo, para los matemáticos, quizás el hecho más importante es que resolver este problema superaría simultáneamente uno de los siete grandes problemas matemáticos del tercer milenio: P versus NP. En 2000, el Instituto de Matemáticas Clay ofreció una recompensa de un millón de dólares por una solución a cada uno de estos problemas, y esta es también una razón (aunque secundaria para los matemáticos altruistas) por la cual cientos de las mejores mentes del planeta han estado trabajando en ello durante varias décadas. El tema del libro se presenta a un alto nivel de especialización: su autor pertenece a un grupo selecto de las figuras más significativas...