Es un problema muy importante para el mundo de la computación. Imagínense, pasándolo a términos prácticos, si descubrimos que P=NP habría una manera de poder resolver cualquier problema computable en tiempo polinomial determinista, i.e. en tiempos humanamente tratables.
Encontré una encuesta que se realizó en el 2002 donde se le preguntaron a varios expertos del área de distintas universidades sobre el problema ¿P=NP? He aquí unos resultados:
¿Cuándo crees que se resuelva P=NP?
Encontré una encuesta que se realizó en el 2002 donde se le preguntaron a varios expertos del área de distintas universidades sobre el problema ¿P=NP? He aquí unos resultados:
¿Cuándo crees que se resuelva P=NP?
- Entre 2002-2009: 5
- Entre 2010-2019: 12
- Entre 2020-2029: 13
- Entre 2030-2039: 10
- Entre 2040-2049: 5
- Entre 2050-2059: 12
- Entre 2060-2069: 4
- Entre 2200-3000: 5
- Nunca se resolverá: 5
¿Cuál será la respuesta?
- P = NP : 9
- P != NP : 61
¿Qué técnicas se usarán en la demostración?
- Técnicas combinatorias y de complejidad: 11
- Lógica: 9
- Matemáticas: 10
- Nuevas técnicas: 16
Hay muchos datos más en la encuesta, por ejemplo algunos investigadores comentan sobre que la solución la dará su universidad, en tal año y usará tal cosa para demostrarla.
El área de complejidad computacional es un mundo lleno de temas divertidos e interesantes. Considero yo que es una de las áreas más importantes en las Ciencias de la Computación.
Yo en particular creo que P != NP, y tú ¿qué piensas? ¿P = NP?
Actualización: No sabía pero me dijo un amigo que en un capítulo de los simpsons está puesta la igualdad, P=NP en el capítulo donde Homero viaja a la tercera dimensión
El área de complejidad computacional es un mundo lleno de temas divertidos e interesantes. Considero yo que es una de las áreas más importantes en las Ciencias de la Computación.
Yo en particular creo que P != NP, y tú ¿qué piensas? ¿P = NP?
Actualización: No sabía pero me dijo un amigo que en un capítulo de los simpsons está puesta la igualdad, P=NP en el capítulo donde Homero viaja a la tercera dimensión
14 comentarios:
determinista != determinístico.
http://es.wikipedia.org/wiki/Sistema_determinista
Pero no me dijiste si P=NP
http://es.wikipedia.org/wiki/Determinista
¬¬
http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing#M.C3.A1quinas_de_Turing_deterministas_y_no_deterministas
Vamos, no te compliques tanto. Sabemos a lo que nos referimos
Chales dificil, muuuy dificil pregunta, por un lado como todo un novato podría decir que nunca tendrá respuestá, por otro lado no tengo suficientes conocimientos matemáticos para poner alguna fecha en especial, mmmmm como diria aquel comercial: "quien sabe, quiza el mundo nunca lo sabrà" a lo mejos será más fácil saber con cuantas chupadas te acabas una tutsi :p, por cierto ¿alguien lo sabe?
(a ver si ahora sí...)Pues yo creo que para toda instancia I de un problema de decisión D en NP existe un algoritmo A_i en P que lo decide, y que existe un algoritmo S también en P que encuentra A_i dados I, D.
Pero que en general para los problemas que conocemos como difíciles el orden de los polinomios va a ser tan grande que no importa.
Eso es lo que pienso. Por ahora, al menos.
Mi otra teoría es que las clases son iguales en lunes, miércoles y viernes, diferentes en domingo, martes y jueves, y es indeterminable los sábados.
Vaya, entonces ¿P=NP para ti Soffer?, es lo que te entendí, cualquier instancia I de un problema en NP existe un algoritmo en P que decide a I.
Sí, pero 'pérame, creo que la regué en grande y puede que eso en realidad demuestre que P != NP. Estoy redactando el post en este momento.
Ya está. Aunque, seguramente, estoy equivocado...
Tiene muchísimos cabos sueltos, pero creo que está interesante y quién sabe, podría funcionar.
Tambien en un cap d futurama salen dos tomos rotulados P y NP q son iguales:
http://11.media.tumblr.com/YC5pHVK7Jl0rlc0khVLpbUOdo1_400.jpg
Gracias Netza, hay mucho geek atras de los libretos de los Simpsons y Futurama
Publicar un comentario