Cultura y divulgación
241 meneos
5558 clics
¿Qué es eso del problema P versus NP?

¿Qué es eso del problema P versus NP?  

En Derivando nos enfrentamos a uno de los siete problemas del milenio, o al menos… a explicar en qué consiste: ¿Qué es el problema P versus NP?

| etiquetas: problema , p , np , derivando
119 122 7 K 390
119 122 7 K 390
  1. He visto algunas antiguas (2006) al respecto pero no funcionan ya... y supongo que no serían vídeo sino texto.
  2. NP = Ni Pajolera
  3. Cosas de transistores.
  4. Vídeo pésimo
  5. Muy bien explicado.
  6. #4 Pues a mi, sin saber mucho sobre el tema, me ha parecido que está muy bien explicado.
  7. #6 Pues a mí no: el vídeo es pésimo
  8. #7 Al margen de que eres libre de tener esa opinión, ¿podrías decirnos por qué te parece pésimo? Por curiosidad.
  9. #8 Joer, es un vídeo que está grabado torpemente y en el que terminan diciendo "si resolvieramos ... entonces resolveríamos..". Es decir, la gilipollez de siempre. NO tiene en cuenta que ésa no es la visión del problema en la actualidad, que trata no de su resolución, sino de su independencia.

    Vamos, que quiere llamar la atención pero se queda en un vídeo aburrido, uno entre cientos y mal editado.
  10. Curioso canal, un video bastante accesible.
  11. #9 Estoy de acuerdo contigo: faltan tetas en el vídeo.
  12. #11 Tetas no hacen falta, pero alguna noción de verdad de complejidad computacional, sí
  13. #12 Halt problem.
  14. #4 Porque tú lo harías mejor. Tu avatar hace honor a tu actitud.
  15. Hay un capítulo de elementary que trata sobre esto mismo.
  16. #9 ¿Puedes explicarme de qué va eso de la independencia?
  17. #12 tío, es para gente que no sabe ni papa. Yo creo que es incluso para niños, date cuenta que se dirige a la audiencia como "los que controléis de esto" y está hablando de una función logarítmica. Tú te crees que a una aundiencia así les vas a explicar complejidad computacional?
  18. #3 Te faltan P's y N's por todas partes para andar medianamente bien encaminado
  19. #6 #4 Por vuestras respuestas esta claro que este vídeo es P = NP porque es tanto pésimo como no pésimo...

    (acepto que me cosáis a negativos por chiste muy malo)
  20. #18 Ahí tienes el problema
  21. Interesante
  22. En el primer capítulo de Numb3rs el protagonista trata de resolver este problema encerrándose en su buhardilla un fin de semana con unas cuantas pizarras y un paquete de tizas.

    Ahí acabé de ver la serie.
  23. #23 Imposible a menos que tu programa sea NaDa.
    www.bernardbelanger.com/computing/NaDa/
  24. #6 A mi sabiendo sobre el tema, me ha parecido bueno como introducción, la única duda de que no sea bueno es que a mi personalmente no me aporta nada así que no sé como lo verá alguien que no sepa del tema. Si a ti te aportado algún concepto intuitivo probablemente sea bueno.

    Quizás podría hablar de otras cosas, pero sería complicarlo, una de las cosas útiles de esto es que si tienes un problema nuevo, antes de perder el tiempo buscando una solución perfecta si demuestras que es equivalente a un problema np-completo, ya puedes empezar a buscar alternativas más razonables.

    PS: Hay una tira de comic que plantea esto como una forma de salvaguardar el ego. xD "Yo no puedo resolver tu problema, pero esta lista de genios matemáticos tampoco pueden, así que no me culpes a mi". :-D
  25. #16 pregúntale a vascos y catalanes verás que risa.
  26. El problema es el siguiente: hay que demostrar que los problemas para los que es fácil encontrar respuesta, es igual de fácil comprobar que la respuesta es correcta.
    ¿Lo he entendido bien?
  27. Uy, sheldon...
  28. #23 El problema de la parada no és Recursivo! Con lo que no puede ser NP ni EXP ni nada.

    Ah y NP no significa No Polinómico. Significa Non-deterministic Polyomial Time.
  29. acabo de revivir mi peor pesadilla en la carrera de informatica
    creo que estaré otra vez un tiempo durmiendo mal
  30. Ya quisieramos muchos haber tenido profesores de mates así!
  31. #27 Acabo de enterarme que ¿P = NP? es otro acto de opresión del estado español. xD xD xD
  32. Hay que entenderlo, señores. Que es donde se diferencia los buenos y malos programadores. Que pensamos que hemos encontrado un chollo de programador porque le pagas 600€ y luego cuando consigues un par de clientes más, entiendes por qué va todo taaaan lento. Programación exponencial, con un cliente funciona pero con 5 tarda un día en enseñarte una pantalla
  33. #33 "Un ejemplo es el problema de la parada. Para deducir si un programa acaba o no su ejecución correctamente habría que comprobar todas las combinaciones posibles de entrada, todos los estados posibles del programa y verificar para cada uno su terminación. Esto es imposible, al menos con lo que sabemos a día de hoy."

    El problema de la parada es imposible, hoy y siempre.
comentarios cerrados

menéame