[c&p] Toda persona que haya tomado un curso en donde se toque el tema de combinaciones y permutaciones es posible que conozca el famoso problema matemático que se bautizó como "El Problema del Vendedor Viajante". Este famoso problema postula que es extremadamente difícil calcular la ruta óptima para que un vendedor visite varias ciudades cuando estas ciudades están a distancias diferentes unas de otras. En términos matemáticos se le considera "NP-Complete / NP-Hard", o "NP-Difícil".
Comentarios
Para complementar: ver el problema uno del milenio http://personales.ya.com/casanchi/mat/milenio00.htm ...
Creo que este problema también se conoce como del Viajante de Comercio (
ver http://es.wikipedia.org/wiki/Problema_del_viajante ). Y sí, siempre se ha considerado NP. Si lo han pasado a O(n) = n² quiere decir que lo han pasado a P, pero como dice #3, no significa que se demuestre que P y NP son equivalentes. Lástima.
De todas maneras, ojo al dato: Se necesitan N^n fotones. De alguna manera, han trasladado la complejidad computacional temporal a l dominio espacial (recursos requeridos). Así que, de alguna manera, sigue estando ahí.
> Según ellos, si tienes suficiente fotones como para que sean al menos N elevado a N fotones ( en donde N es la cantidad de ciudades), entonces el problema se puede resolver.
No lo entiendo, se supone que con puedes resolver cualquier problema NP con "n elevado a n", ¿no?
Y de ahí la importancia de los qubits y la computación cuántica...
#2, no han reducido el problema del viajante a P, sino a cuadrático.
No es lo mismo que demostrar el P=NP.