Posts: 887
Threads: 22
Joined: Jul 2017
Localización: Waterloo
Sexo: Hombre
https://arxiv.org/pdf/1708.03486v1.pdf
Norbert Blum ha propuesto esa solución al problema (intenta demostrar que P != NP). Está basado ligeramente en este paper:
https://www.cs.toronto.edu/~toni/Courses...notone.pdf pero intentando adaptar la técnica para circuitos no monotone. Ahora mismo el paper está en review y seguramente no se sepa nada hasta dentro de una semana.
Yo apuesto a que se lo rechazarán, la verdad, pero es intersante de todos modos
.
Pa los que no lo sepan, P vs. NP es uno de los siete "Problemas del milenio" (con un premio de millón de dólares) y con una importancia enorme en el área de ciencias de la computación. Si se demuestra que P=NP puede revolucionar muchas cosas y si se demuestra lo contrario (el presente caso intenta demostrar eso), no cambia mucho salvo que se confirma lo que todos temíamos.
Posts: 3,824
Threads: 129
Joined: Jul 2017
Localización: A Coruña
Sexo: Hombre
Lo vi en hackernews pero no lo lei aún
Posts: 939
Threads: 6
Joined: Jul 2017
Localización: Sant Iscle de Vallalta
Sexo: Hombre
A mi modo de ver, P = NP tiene peores implicaciones que P != NP de cara al funcionamiento de nuestra sociedad. Si P != NP, en particular existen problemas para los cuales ningún algoritmo puede hallar una solución en tiempo polinómico, y eso es bueno en criptografía y, en general, para la seguridad de la información, tanto personal como gubernamental. Si P = NP, la consecuencia inmediata es que somos algo torpes y no hemos dado con la forma de resolver muchos problemas de manera eficiente, pero es cuestión de tiempo que alguien dé con soluciones para distintos problemas, algunos de los cuales pueden llevar a graves fallos en la seguridad nacional de distintos paises y gobiernos.
Pasa un poco como con la existencia de civilizaciones alienígenas: todos parecen querer que existan cuando toda la evidencia recopilada hasta el momento apunta de manera abrumadora hacia su inexistencia, mientras que cualquier análisis sosegado de las implicaciones que tendría su existencia no tardan en convencer a uno de que es mejor que no la haya.
Posts: 887
Threads: 22
Joined: Jul 2017
Localización: Waterloo
Sexo: Hombre
(15-08-2017, 03:55 PM)Jaime Wrote: A mi modo de ver, P = NP tiene peores implicaciones que P != NP de cara al funcionamiento de nuestra sociedad. Si P != NP, en particular existen problemas para los cuales ningún algoritmo puede hallar una solución en tiempo polinómico, y eso es bueno en criptografía y, en general, para la seguridad de la información, tanto personal como gubernamental. Si P = NP, la consecuencia inmediata es que somos algo torpes y no hemos dado con la forma de resolver muchos problemas de manera eficiente, pero es cuestión de tiempo que alguien dé con soluciones para distintos problemas, algunos de los cuales pueden llevar a graves fallos en la seguridad nacional de distintos paises y gobiernos.
Pasa un poco como con la existencia de civilizaciones alienígenas: todos parecen querer que existan cuando toda la evidencia recopilada hasta el momento apunta de manera abrumadora hacia su inexistencia, mientras que cualquier análisis sosegado de las implicaciones que tendría su existencia no tardan en convencer a uno de que es mejor que no la haya.
Dije que P=NP revolucionaría cosas, no que sería una buena revolución. Estoy de acuerdo contigo, lo mejor que nos puede psar es que la otra alternativa.
