Matemáticas o Informática
¿Y si el ordenador más potente del mundo necesitara miles de millones de años para planificar la ruta de un repartidor? Ese es el problema del viajante, y es el ejemplo estrella de P versus NP, una de las grandes preguntas abiertas de la informática 🧮.
La idea es sencilla de contar. Hay problemas que un ordenador resuelve en un tiempo razonable (la clase P) y otros cuya solución, si alguien te la da, se comprueba rápido (la clase NP). La duda es si ambas clases son la misma cosa. Stephen Cook la formuló en 1971 y un año después se publicó una lista de decenas de problemas que parecen fuera del alcance de las máquinas.
Lo más llamativo es que los problemas NP completos funcionan como una llave maestra: si se lograra resolver con eficiencia uno solo, caerían todos los de NP. Por eso es uno de los siete Problemas del Milenio y el Clay Mathematics Institute ofrece un millón de dólares por resolverlo. Cook cree que P y NP son distintos, pero a día de hoy la respuesta honesta sigue siendo «no se sabe». Para este curso es una buena forma de ver por qué no basta con tener ordenadores más rápidos: importa cómo crece el trabajo con el tamaño del problema. El artículo está en español, por si quieres leer la historia de Cook.