El caso es que aunque P=NP, seguiría existiendo problemas que no estarían en P.
Además, el segundo párrafo de #35 tampoco convence, donde dices que los informáticos nos conformamos con encontrar un camino subóptimo y para ello resolvemos un problema que está fuera del conjunto NP.
Como dije en #35 llegar a este tipo de compromiso tiempo/calidad-solución nos ocurre tanto a humanos como a la propia naturaleza en sus soluciones. Y no sólo en este problema del viajante de comercio, en muchísimos otros.
No sé si eres informático universitario (no lo digo por discriminar a nadie, pero en otros niveles educativos de la informática no se suele estudiar teoría de la computación), te lo digo, porque a este tipo de soluciones se les llama heurísticas y es mucho más común de lo que tú crees.
Resolver hasta el óptimo el problema del viajante de comercio para 2000 ciudades aproximadamente pueden ser meses o años de computación. Si tienes un sistema crítico donde necesitas una solución en escasos segundos, no tienes más remedio que usar alguna técnica heurística.
La naturaleza lo hace, una colmena de abejas no se puede permitir el lujo de tardas tanto tiempo en encontrar alimento. Aplican su propio heurístico y que nosotros hemos copiado: "heurístico de la colonia de insectos". O si tu trabajas en una empresa de reparto qué haces: echas un vistazo al mapa y construyes tu propia solución (los humanos somos buenos en esto) o te sientas en una mesa con papel y bolígrafo y te pones a calcular la solución.
#52#44 y #50 El problema del viajante de comercio está demostrado que pertenece a la clase NP-completo. Eso está demostrado matemáticamente. Así que, por mucho que queramos y inventemos la máquina que inventemos, no lo cambiará.
Lo que no está demostrado es la pregunta ¿P = NP? La comunidad científica sospecha que no son iguales y está pendiente de que se admita esta:
En el casi improbable caso de que P=NP, el problema del viajante de comercio es NP-completo, es decir, la clase de problemas más difíciles de NP. Y para los NP-completo existe otra sospecha de la comunidad científica, y es la clase NP-completa no pertenecería a P, en el caso de que P=NP.
En definitiva, sería más fácil pincharme con la aguja del pajar, antes que encontrar una solución en tiempo polinómico al problema del viajante de comercio.
Te pongo un diagrama de Venn donde verás bien como quedan los conjuntos con ambas hipótesis:
es.wikipedia.org/wiki/Archivo:P_np_np-completo_np-hard.svg
El caso es que aunque P=NP, seguiría existiendo problemas que no estarían en P.
Además, el segundo párrafo de #35 tampoco convence, donde dices que los informáticos nos conformamos con encontrar un camino subóptimo y para ello resolvemos un problema que está fuera del conjunto NP.
Como dije en #35 llegar a este tipo de compromiso tiempo/calidad-solución nos ocurre tanto a humanos como a la propia naturaleza en sus soluciones. Y no sólo en este problema del viajante de comercio, en muchísimos otros.
No sé si eres informático universitario (no lo digo por discriminar a nadie, pero en otros niveles educativos de la informática no se suele estudiar teoría de la computación), te lo digo, porque a este tipo de soluciones se les llama heurísticas y es mucho más común de lo que tú crees.
Resolver hasta el óptimo el problema del viajante de comercio para 2000 ciudades aproximadamente pueden ser meses o años de computación. Si tienes un sistema crítico donde necesitas una solución en escasos segundos, no tienes más remedio que usar alguna técnica heurística.
La naturaleza lo hace, una colmena de abejas no se puede permitir el lujo de tardas tanto tiempo en encontrar alimento. Aplican su propio heurístico y que nosotros hemos copiado: "heurístico de la colonia de insectos". O si tu trabajas en una empresa de reparto qué haces: echas un vistazo al mapa y construyes tu propia solución (los humanos somos buenos en esto) o te sientas en una mesa con papel y bolígrafo y te pones a calcular la solución.