domingo, 17 de mayo de 2009

¿P=NP? La encuesta

Una de las preguntas más famosas relacionadas con la Teoría de la Computación que aún no tienen respuesta es el famoso ¿P=NP? P es una clase de complejidad que representa a los problemas para los cuales se conocen algoritmos que pueden resolverlos en tiempo polinomial determinista. NP es una clase de complejidad que representa a los problemas para los cuales se conocen algoritmos que pueden resolverlos en tiempo polinomial no-determinista, pero no se conocen algoritmos que puedan resolverlos en tiempo polinomial determinista (p.e. Agente Viajero, Satisfacibilidad, The Hamiltonian Path Problem).
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?
  1. Entre 2002-2009: 5
  2. Entre 2010-2019: 12
  3. Entre 2020-2029: 13
  4. Entre 2030-2039: 10
  5. Entre 2040-2049: 5
  6. Entre 2050-2059: 12
  7. Entre 2060-2069: 4
  8. Entre 2200-3000: 5
  9. Nunca se resolverá: 5
¿Cuál será la respuesta?
  1. P = NP : 9
  2. P != NP : 61
¿Qué técnicas se usarán en la demostración?
  1. Técnicas combinatorias y de complejidad: 11
  2. Lógica: 9
  3. Matemáticas: 10
  4. 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



14 comentarios:

Michael, the kid dijo...

determinista != determinístico.

Memo dijo...

http://es.wikipedia.org/wiki/Sistema_determinista

Pero no me dijiste si P=NP

Michael, the kid dijo...

http://es.wikipedia.org/wiki/Determinista

Memo dijo...

¬¬

Memo dijo...

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

magicorlan dijo...

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?

jsoffer dijo...
Este comentario ha sido eliminado por el autor.
jsoffer dijo...
Este comentario ha sido eliminado por el autor.
jsoffer dijo...

(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.

Memo dijo...

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.

jsoffer dijo...

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.

jsoffer dijo...

Ya está. Aunque, seguramente, estoy equivocado...

Tiene muchísimos cabos sueltos, pero creo que está interesante y quién sabe, podría funcionar.

Netzaaa! dijo...

Tambien en un cap d futurama salen dos tomos rotulados P y NP q son iguales:

http://11.media.tumblr.com/YC5pHVK7Jl0rlc0khVLpbUOdo1_400.jpg

Memo dijo...

Gracias Netza, hay mucho geek atras de los libretos de los Simpsons y Futurama