EDICIóN GENERAL
241 meneos
5514 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 487 cultura
119 122 7 K 487 cultura
He visto algunas antiguas (2006) al respecto pero no funcionan ya... y supongo que no serían vídeo sino texto.
NP = Ni Pajolera
Cosas de transistores.
#3 Te faltan P's y N's por todas partes para andar medianamente bien encaminado
#18 Ahí tienes el problema
Vídeo pésimo
#4 Pues a mi, sin saber mucho sobre el tema, me ha parecido que está muy bien explicado.
#6 Pues a mí no: el vídeo es pésimo
#7 Al margen de que eres libre de tener esa opinión, ¿podrías decirnos por qué te parece pésimo? Por curiosidad.
#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.
#9 Estoy de acuerdo contigo: faltan tetas en el vídeo.
#11 Tetas no hacen falta, pero alguna noción de verdad de complejidad computacional, sí
#12 Halt problem.
#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?
#9 ¿Puedes explicarme de qué va eso de la independencia?
#16 pregúntale a vascos y catalanes verás que risa.
#27 Acabo de enterarme que ¿P = NP? es otro acto de opresión del estado español. xD xD xD
#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)
#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…   » ver todo el comentario
#4 Porque tú lo harías mejor. Tu avatar hace honor a tu actitud.
Muy bien explicado.
Curioso canal, un video bastante accesible.
Hay un capítulo de elementary que trata sobre esto mismo.
Interesante
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.
Si P = NP entonces significa que todo problema No resoluble en tiempo Polinómico se podría reducir a un problema resoluble en tiempo Polinómico. Lo cual para cosas como la criptografía significaría el fin de la seguridad. Para cosas como la planificación de rutas, horarios, optimización de circuitos para minimizar su área, etc. implicaría una mejora bestial. Actualmente para ese tipo de cosas no se emplean algoritmos exactos porque son exponenciales así que hay que conformarse con heurísticas…   » ver todo el comentario
#23 Imposible a menos que tu programa sea NaDa.
www.bernardbelanger.com/computing/NaDa/
#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.
#30 no he dicho que sea recursivo. np es la categoría de problemas no decidibles en tiempo polinómico.
#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.
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?
Uy, sheldon...
acabo de revivir mi peor pesadilla en la carrera de informatica
creo que estaré otra vez un tiempo durmiendo mal
Ya quisieramos muchos haber tenido profesores de mates así!
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
comentarios cerrados

menéame