#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?
#6:
#4 Pues a mi, sin saber mucho sobre el tema, me ha parecido que está muy bien explicado.
#11:
#9 Estoy de acuerdo contigo: faltan tetas en el vídeo.
#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?
#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.
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?
#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.
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 que te dan una solución que aproxima el óptimo. Para muchos problemas la aproximación ronda el 80-90% del óptimo, lo cual pienso que está muy bien.
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.
No está demostrado que los problemas de clase NP se puedan transformar en problemas de clase P, pero tampoco está demostrado que no se puedan transformar.
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.
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
#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. "Yo no puedo resolver tu problema, pero esta lista de genios matemáticos tampoco pueden, así que no me culpes a mi".
Comentarios
#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?
Muy bien explicado.
NP = Ni Pajolera
Curioso canal, un video bastante accesible.
#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 ¿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.
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?
#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.
He visto algunas antiguas (2006) al respecto pero no funcionan ya... y supongo que no serían vídeo sino texto.
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 que te dan una solución que aproxima el óptimo. Para muchos problemas la aproximación ronda el 80-90% del óptimo, lo cual pienso que está muy bien.
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.
No está demostrado que los problemas de clase NP se puedan transformar en problemas de clase P, pero tampoco está demostrado que no se puedan transformar.
#23 Imposible a menos que tu programa sea NaDa.
http://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.
Cosas de transistores.
#3 Te faltan P's y N's por todas partes para andar medianamente bien encaminado
#18 Ahí tienes el problema
Interesante
Ya quisieramos muchos haber tenido profesores de mates así!
Hay un capítulo de elementary que trata sobre esto mismo.
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.
Uy, sheldon...
acabo de revivir mi peor pesadilla en la carrera de informatica
creo que estaré otra vez un tiempo durmiendo mal
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
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
#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)
#19
#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.
"Yo no puedo resolver tu problema, pero esta lista de genios matemáticos tampoco pueden, así que no me culpes a mi".
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.
#4 Porque tú lo harías mejor. Tu avatar hace honor a tu actitud.