En este trabajo, se presenta un sencillo problema de Sendero llamado grafo multietapa (MSP) y se muestra que el problema del circuito Hamiltoniano (HC)puede ser polinómicamente reducible al problema MSP. Para resolver el problema MSP, se propone un algoritmo polinomial y probar su NP-completo. El resultado implica NP = P.
Tendría que leerme el articulo antes de comentar nada (treinta y pico páginas) pero si es cierto lo que da a entender la entradilla sería un descubrimiento de la ostia, digno de ganar el premio turing.
El circuito Hamiltoniano tiene una complejidad N!, siendo NP-Duro, que se pueda resolver en tiempo polinomio sería algo increíble.
PD: Espero no haber metido la pata al soltar algo de lo anterior
PDD: Si alguien lee el articulo y ve que hay algún "truco" ¡qué lo comente!
#7 no es que sea baladí, es que no lo ha demostrado ¿crees que sí eso fuese así saldría antes en Arxiv que en los periódicos? Este tipo de "pruebas" aparecen al menos una vez al año
#11#12 Me alegro. Digo yo que en algún sitio lo tendrá que publicar primero, otra cosa es que me digas que no lo ha podido publicar más que en arxiv porque en cualquier otro sitio no se lo aceptarían, pero aún no te he visto dar ni una razón de por qué crees que no es correcto o no lo ha demostrado. Tal vez pienses que si no ha pasado la revisión de pares no merezca la pena perder tu tiempo en darnos algunas claves.
#3 El problema es que resuelto un NP, resueltos todos, la prueba se puede extender fácilmente, y esto afectaría por ejemplo a la supuesta inviolabilidad de los sistemas criptográficos.
#3#5#8 Esto es más ridículo que los que dijeron que los neutrinos podían superar la velocidad de la luz. Vamos, que si estos han descubierto que P = NP me lo tatuo en el culo.
explican un poco más el paper y en https://news.ycombinator.com/item?id=5785693 tienen una interesante discusión acerca de su validez. La conclusión que yo saco es que el autor no ha formalizado de la mejor manera el problema, hay quien tiene dudas por sus citas bibliográficas y por su engorrosa explicación, pero es arxiv, un repositorio que no tiene revisión de pares, así que tu culo y el resto del mundo tendremos que esperar.
Comentarios
Tendría que leerme el articulo antes de comentar nada (treinta y pico páginas) pero si es cierto lo que da a entender la entradilla sería un descubrimiento de la ostia, digno de ganar el premio turing.
El circuito Hamiltoniano tiene una complejidad N!, siendo NP-Duro, que se pueda resolver en tiempo polinomio sería algo increíble.
PD: Espero no haber metido la pata al soltar algo de lo anterior
PDD: Si alguien lee el articulo y ve que hay algún "truco" ¡qué lo comente!
Ya se sabía, en un capítulo de Futurama salen dos libros, P y NP y tienen el mismo tamaño!
Sí, vamos, que ha resuelto el problema P=NP....
Povale
#3 http://es.wikipedia.org/wiki/Problemas_del_milenio#P_versus_NP ... baladí no es.
#7 no es que sea baladí, es que no lo ha demostrado ¿crees que sí eso fuese así saldría antes en Arxiv que en los periódicos? Este tipo de "pruebas" aparecen al menos una vez al año
#11 #12 Me alegro. Digo yo que en algún sitio lo tendrá que publicar primero, otra cosa es que me digas que no lo ha podido publicar más que en arxiv porque en cualquier otro sitio no se lo aceptarían, pero aún no te he visto dar ni una razón de por qué crees que no es correcto o no lo ha demostrado. Tal vez pienses que si no ha pasado la revisión de pares no merezca la pena perder tu tiempo en darnos algunas claves.
#3 El problema es que resuelto un NP, resueltos todos, la prueba se puede extender fácilmente, y esto afectaría por ejemplo a la supuesta inviolabilidad de los sistemas criptográficos.
JAJAJAJAJAJAJAJAJAJA
P = NP
JAJAJAJAJAJAJA
No.
#3 #5 #8 Esto es más ridículo que los que dijeron que los neutrinos podían superar la velocidad de la luz. Vamos, que si estos han descubierto que P = NP me lo tatuo en el culo.
#9 En
explican un poco más el paper y en https://news.ycombinator.com/item?id=5785693 tienen una interesante discusión acerca de su validez. La conclusión que yo saco es que el autor no ha formalizado de la mejor manera el problema, hay quien tiene dudas por sus citas bibliográficas y por su engorrosa explicación, pero es arxiv, un repositorio que no tiene revisión de pares, así que tu culo y el resto del mundo tendremos que esperar.#8 perdona, pero sé lo que es un problema NP-completo, no necesito que me lo expliques.
Vale ya se lo que es el circuito hamiltoniano, Podian haber puesto que era la teoria de grafos e igual se entendia mejor.
En una primera lectura de la entradilla, yo pondría esto a la altura de los generadores de energía libre.
De momento me abstengo de votar nada.
Categoria ciencia confusa Ya!! "ironic off"