#56 No he visto el comentario hasta ahora, imagino que ya no lo leerás pero respondo de todas maneras
Te pongo un diagrama de Venn donde verás bien como quedan los conjuntos con ambas hipótesis:
http://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.
#35 "El problema del viajante de comercio es un problema de optimización combinatoria y pertenece a la clase NP, es decir..." ... se puede resolver en tiempo polinómico en una máquina no determinista.
Creo yo
#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:
http://ciencia.barrapunto.com/ciencia/10/08/09/080213.shtml
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.
http://es.wikipedia.org/wiki/NP-completo
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.
#52 Sí, si estamos de acuerdo. Esa intuición tenemos, eso se cree y eso pensamos. ¡Pero falta demostrarlo! jeje
Que sólo era por poner la puntillina hombre, no te quitaba la razón, para una vez que tocamos un tema que me gusta y del que sé un poquito me apetecía pedantear.
#52
???
No me entero (y además no veo esas líneas en el enlace que pones)...
Premisas:
NP es el conjunto de problemas que se pueden resolver en tiempo polinomial en una máquina no determinista
NP-completo es el conjunto de los problemas más difíciles de resolver del conjunto NP.
P es el conjunto de problemas que pueden ser resueltos en tiempo polinomial por una máquina determinística. No se sabe con seguridad todavía si P es un subconjunto propio de NP, pero se cree que sí.
Entonces,
como el conjunto NP-completo es un subconjunto de NP, si se llega a demostrar que el conjunto P es igual al conjunto NP -> eso quiere decir que el conjunto NP-completo también sería un subconjunto de P.
Otra cosa distinta sería que se demostrara que P = (NP - NP-completo)
¿Qué opinas?
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.
#56 No he visto el comentario hasta ahora, imagino que ya no lo leerás pero respondo de todas maneras
Te pongo un diagrama de Venn donde verás bien como quedan los conjuntos con ambas hipótesis:
http://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.
#32 #39 #41 #42 ¿qué parte de "que varíe en función del coste de la vida" no he pillado yo?
Veo el problema que planteáis... pero si doblar el salario conlleva que se doble
el coste de la vida... y el salario se define en función del coste de la vida....
no es que nos quedemos como estábamos, sino que habrá que
volver subir el salario mínimo para adecuarlo al nuevo coste de la vida!!! :-
Así que alguna medida habrá que tomar para que no ocurra lo que habéis predicho... ya que sino
acabaríamos cobrando infinito y la vida en españa sería 2xinfinito (y no creo que desde Europa
nos consientan esa inflación ).
#4 Sip, y además me pareció una tira flojita respecto a lo que suele aparecer...
Un gran día para la familia de los Milito.
Liga + Scudetto el mismo día
#4 ¿no conocías infojobs?
#5 Me quiere sonar algo de un acuerdo sobre comprar petróleo a 100 dólares...
[Pero no tengo ni idea acerca de si lo estamos haciendo ahora]
Jue! pues me ha dao penica Policarpo ;(
No sé si yo estoy sensiblón o es que ha redactado la noticia La gente de Bart
#15 Glups! He leído todo pero, a la hora de escribir, he recordado la última palabra de la frase.
Debo tener un problema de almacenamiento o algo
¿Quién es el encargado español de hacer el intercambio?
Es por saber si es factible apostar a que volvemos de la cumbre sin ninguna bandera...
#3 Difícil jugar incluso al Pong.
Yo vaticino un enorme espacio de direccionamiento.
#3 Debemos sentirnos orgullosos por los pocos meses que han sido
necesarios para terminar con la peor empresa de España. Eso es eficiencia
Bueno, si siguen así y vuelven a llevarse el trofeo, el próximo año pueden volver
a cambiar de nombre y ya'sta!
#12 Ya se le ha costado un párpado al menos....
...,_ utiliza un rudimentario pedazo de vidrio adaptado a una aguja y para pintar nada más y nada menos que una “carísima” pestaña extraída de uno de sus parpados.
Ya sabemos que la solución pasa por coger hielo del cometa Halley (*), pero como el próximo acercamiento no es hasta el 2061 (**) ...
podemos ir pensando alguna alternativa de estas, para que no nos pille el toro y eso.
(*) http://en.wikipedia.org/wiki/Crimes_of_the_Hot
(**) http://es.wikipedia.org/wiki/Cometa_Halley
#3 Larga vida a Futurama..
#1 Discrepo.
Si el planeta se viese plano, indicaría que respiramos en mucho menos espesor.
Lo que muestra la foto quiere decir que hay materia más pesada que el helio al menos hasta la altura
suficiente como para apreciar la curvatura del planeta.
Corrígeme si me equivoco.
#52
???
No me entero (y además no veo esas líneas en el enlace que pones)...
Premisas:
NP es el conjunto de problemas que se pueden resolver en tiempo polinomial en una máquina no determinista
NP-completo es el conjunto de los problemas más difíciles de resolver del conjunto NP.
P es el conjunto de problemas que pueden ser resueltos en tiempo polinomial por una máquina determinística. No se sabe con seguridad todavía si P es un subconjunto propio de NP, pero se cree que sí.
Entonces,
como el conjunto NP-completo es un subconjunto de NP, si se llega a demostrar que el conjunto P es igual al conjunto NP -> eso quiere decir que el conjunto NP-completo también sería un subconjunto de P.
Otra cosa distinta sería que se demostrara que P = (NP - NP-completo)
¿Qué opinas?
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.