El investigador Vinay Deolalikar publica una solución a uno de los problemas del milenio: P vs NP

#1   Explicación del problema es.wikipedia.org/wiki/P_versus_NP

#2   ¿Que aplicaciones tendría esta solución?

#3   A lo largo de varios años ya han habido varios intentos de solución. Si al revisarse se comprueba es valida, felicidades por el investigador, que podrá pasar a recoger su premio de $1.000.000 y de paso los expertos en seguridad criptográfica podrán descansar tranquilos al saber que P != NP.

#4   #2 En principio ninguna, lo chulo hubiese sido que P = NP pero por lo menos ahora, si la prueba llega a ser cierta, toda la gente que se dedicaba a investigar esto se dedicaran a algo útil.

#5   #4
se dedicaran a algo útil.

Siempre ha sido algo útil. No hay nada más útil que dejar una pregunta de éste calibre con una buena respuesta, sea cual sea y por mucho que la respuesta sea una que ya se intuía debido a todos los intentos que han habido por encontrar P = NP.

lo chulo hubiese sido que P = NP

Ya te digo yo que éso de chulo no tendría nada. Agencias como la NSA y su software se podrían ir a la mierda si una vez demostrado que P = NP la gente empezase a encontrar reducciones de problemas NP a P. Las comunicaciones seguras serían una ilusión.

#6   Lo bueno de estudiar ingenirías es que no te metes en estos jaleos salvo por devoción personal.

#8   Para #5, algo de razón #4. Es cierto que saber este resultado es muy importante, pero también hay mucha gente que se dedica a resolver problemas difíciles como éste y nunca llega a respuesta alguna en toda su vida. Basta recordar la cantidad de gente que quedó loca tratando de demostrar que existía otro infinito entre el aleph 0 y 1.

A todo esto, si mal no recuerdo, creo que una entrada similar ocurrió el año pasado, con otro tipo (no sé si habrá llegado a portada), que decía haber probado que P!=NP y que estaba en revisión su demostración...creo que el archivo se podía descargar desde arxiv...

Hace un tiempo atrás tuve clases de complejidad computacional con un profesor que hizo su doctorado en el MIT y fue discípulo de Sipser. Y bueno, contaba que siempre aparecían este tipo de publicaciones y que demoraba su tiempo hasta encontrar el error. Esperemos que este no sea el caso y se cierre el tema. Pero primero debe pasar por muchas manos antes su aprobación final.

#9   Se me olvidaba:

www.hpl.hp.com/personal/Vinay_Deolalikar/

#10   y yo con estos pelos

#11   Bueno, si se demuestra es una increible noticia para todos los científicos que publicaron papers bajo la hipótesis (lógica) de la desigualdad entre P y NP. Sea como sea todo el proceso para intentar atacar al problema ha dado como resultado un montón de estudios y publicaciones interesantes (y útiles) en muchos campos de las ciencias de la computación.

Enhorabuena al el investigador indio que ha publicado el paper y esperemos que la demostración sea correcta.

#12   Si no voy mal, P=NP implicaría que no existen problemas de complejidad más allá de los polinómicos. Eso querría decir que, para aquellos problemas que ahora mismo son exponenciales o peores, existen algoritmos mejores, sólo que no los hemos encontrado. Eso sería una putada importante para temas como la criptografía, que se basa en que factorizar un número en sus primos es un problema exponencial (o factorial, no recuerdo). Si resulta que existe un algoritmo polinómico, la mayoría de sistemas de cifrado se van al garete en cuanto se descubra (que sabiendo que existe sería cuestión de tiempo).

Por tanto, si resulta que P!=NP, quiere decir que sí existen problemas intrínsecamente no polinómicos. Eso sí, hasta donde yo sé, el hecho de que existan no quiere decir que se pueda saber a priori cuáles son, o identificar si uno en concreto lo es o no. Por ejemplo, por mucho P!=NP, ahora habría que ver si el tema de la factorización en primos es en realidad NP, que igual resulta que no lo es y mañana alguien inventa un algoritmo lineal... Pero al menos se sabe que existe la posibilidad de que lo sea. En cambio, si P=NP, ya sabríamos a ciencia cierta que es un problema resoluble polinómicamente, y por tanto que se rompa toda la criptografía existente sería sólo cuestión de tiempo.

En fin, esa es mi interpretación de todo esto. Si he metido mucho la gamba, que alguien más experto lo aclare un poco...

#13   #12 Va más allá que todo eso. Si se demostrase P=NP está demostrado que la demostración debería traer implícita un método para transformar problemas NP (resolubles en tiempo polinomial en una máquina no determinista, "nondeterministic polynomial time") a P, y esa transformación sería en tiempo polinomial, por lo que no sería necesario encontrar ningún algoritmo.

Pero vaya, que P hasta ahora se considera distinto de NP por la gran mayoría aunque no exista demostración verificada (por ahora).

#14   #7
Criptografía cuántica... parece que lo único que asegura es el canal de transmisión, pero no los datos en sí. Y la forma de asegurar el canal de transmisión se basa en que la observación del mismo es imposible puesto que cambia el estado de la información transmitida y por tanto ya no sirve.
Si logras infiltrarte en el ordenador de alguien, sus datos seguirán cifrados con métodos normales y podrías descifrar todo lo que tiene "fácilmente".

Y una vez tuvieras ordenadores cuánticos, el problema seguiría existiendo. Simplemente cambias bits por Qubits de tres estados en vez de dos (0,1, 0 y 1), que sí, dan cuerda para nuevos algoritmos y hace que algunos problemas difíciles (NP) se puedan tratar como P, al poder realizar varias tareas a la vez. Pero si P=NP, entonces esa ventaja dejaría de existir también.

Así lo entiendo yo.

#15   Es una pregunta que todos los grandes pensadores se han hecho.
www.cs.umbc.edu/~chang/cs641.s01/homer.p=np.jpg

#16   Había leído algo en Gaussianos gaussianos.com/pues-igual-resulta-que-p-np/ esta mañana

#17   Según cuenta Lubos Motl en "HP Labs researcher: P ≠ NP," The Reference Frame, August 09, 2010 (motls.blogspot.com/2010/08/hp-labs-researcher-p-is-not-np.html), la prueba tiene muy buena pinta, pero por lo que parece ya se han encontrado varios fallos (lo que no sabe aún es si son errores menores que se podrán resolver de forma fácil o si invalidarán la prueba completa).

Son buenas noticias justo antes del inicio del ICM 2010 en la India. Habrá que estar al loro.

#18   No sé si habrá alguien que pueda estar interesado en lo que yo pueda contar sobre este asunto (que me pilla muy lejos), aún así me permito el lujo de recomendar "Una copa de cava y la demostración de P≠NP de Vinay Deolalikar" ( francisthemulenews.wordpress.com/2010/08/09/una-copa-de-cava-y-la-demo ).

#19   Si a Perelman, con lo que es ese hombre, se le pidieron unos años de rigor y la prudencia aconsejada ante su prueba de la Conjetura de Poincaré lo menos que podemos hacer es recoger esta noticia con el escepticismo necesario aunque también con respeto al trabajo de este investigador.

#20   Bueno, he leido artículos anteriores de este investigador y no es de esos desconocidos que envían una prueba de P/=NP a Arxiv. Aunque personalmente dudo de que la prueba sea completa, la línea de ataque que sigue ya había sido calificada de prometedora por Cook.

De todas formas, y visto que la ha enviado a varios colegas, las pegas que estos le pongan van a llevar tiempo en resolverlas, si se pueden todas.

#21   20 Comentarios, y no se de que hablamos...
Me voy a otra noticia ...

#22   #12 Si no voy mal, P=NP implicaría que no existen problemas de complejidad más allá de los polinómicos.

Lamento decirte que vas mal, muy mal. P=NP implicaría que muchos problemas que actualmente son exponenciales dejarian de serlo, pero los problemas inherentemente exponenciales (los de la clase EXP) seguirían siéndolo.

Recuerda que NP es el conjunto de problemas cuya solución se calcula en tiempo exponencial, pero puede verificarse en tiempo polinómico. Es difícil calcular los factores de un producto de dos números primos, pero si te dicen cuál es la solución se puede verificar con una vulgar multiplicación.

#23   Flipo que esto no esté en portada ya.
Me parece que aunque no esté confirmado del todo esta noticia es lo más importante que le ha pasado a la computabilidad en la vida.
Joer, que el problema P=?NP es el problemazo del milenio.

Bueno, lástima que no la pueda votar por "ser clon"

#24   #23 no es "el problema" es uno de ellos.

#25   Me encantan los comentarios de Slashdot:
I mean, NP has an N in front of the P. That's obviously not the same as P.
TR: Quiero decir, NP tiene una N en frente de la P. Eso obviamente no es lo mismo que P.

Si sólo se hubiesen dado cuenta de eso antes...

#26   #24 Tienes toda la razón, pero eso no quita que me sorprenda lo que le cuesta llegar a portada.
Como dice #25 al final va a ser irrelevante... mira que no ver la "N"... ainss

#27   Si demostraciones sobre esto son tan habituales, ¿por qué a esta se le presta atención? (Ojo, que me alegraría un montón si se confirmara su validez)

#28   www.lafferty.ca/files/stuff/misc/futurama_p_np.png

#29   #21 Resumen aproximado y simplificado (hace tiempo que estudié esto)

Digamos que hay ciertos problemas que se resuelven mediante un algoritmo (o un programa informático, para entendernos)

En #7 hay algunos ejemplos. Cifrado de datos, búsquedas en textos, problemas de logística (mejor camino para enviar cosas de un lado a otro), reconocimiento de imágenes, operaciones matemáticas varias.

Algunos de estos problemas se resuelven en tiempo polinómico y otros no. Dicho de otra forma, y para que se entienda:

- Hay soluciones que resuelven un problema que tardan muchisimo tiempo en encontrar la solución
- Hay soluciones que resuelven un problema y además lo hacen en poco tiempo

Puede que alguna vez hayáis leído cosas como "para romper la seguridad de una red WiFi habría que tener a un ordenador haciendo cálculos durante 20 años" o algo similar.

Es decir que todo problema tiene solución, pero algunas soluciones son tan lentas que a efectos prácticos no son válidas.

¿En que consiste el problema P y NP? Bien pues consiste en tratar de averiguar si para cualquier problema existe una solución válida y que se pueda calcular en un tiempo razonable.

Si P es igual a NP => Implica que para cualquier problema matemático se puede encontrar una solución válida y que resuelva el problema en un tiempo razonable
Si P es distinto a NP => Implica que existen problemas matemáticos para los cuales, aún existiendo soluciones, las soluciones serán siempre demasiado lentas como para poder ser aplicadas (ejemplos de este tipo de problemas en #7 )

Espero no haber dicho ninguna burrada, ya he comentado que hace tiempo que estudié esto.

#30   Lo que yo no entiendo, es que con lo frikis que somos a veces, como está noticia todavía no está en la portada.