Hace un par de meses quería crear un algoritmo para ayudar a mi padre con un problema de contabilidad, y gracias a su vídeo me doy cuenta que posiblemente era un NP-Completo, y que sin saberlo estaba buscando solución a uno de los problemas del milenio 😂, no lo continué por falta de tiempo, pero ahora, aunque ya no es necesario lo voy a intentar por diversión. Si lo resuelvo les dejo medio millón por la explicación 👌😂
Hola un cordial saludo; he intentado presentar la solución a este problema matemático informático pero se me ha dificultado porque me piden seder mis derechos de autor. Que puedo hacer ? Se los agradecería. Mil gracias
Muy bien explicado! Después de 25 años, me he enterado de que van los problemas P y NP. Yo era de los que creían que los NP no eran computacionables y punto... Gracias.
muy bueno el vídeo y la explicación. La sección de preguntas y respuestas tengo que decir que , aunque resulta muy interesante el ejemplo, me parece que dais dos veces la misma definición para problemas distintos y me acaba liando un poco.
Hola me pueden hacer el favor de regalarme le contacto para dar respuesta a este tema, llevo rato intentando comunicarme pero no me ha sido posible... Gracias
Gracias por aclarar un concepto que muchos se han encargado de nublar. Por cierto, los videos se renderizan (aún no reconocido por la RAE), los programas se compilan.
Cordial saludo señores Los 3 Chanchitos; Me gustaria saber si me pueden colaborara para contactar al Instituto Clay de Matematicas para revision de un problema matematico. Gracias
Genial, gracias por el esfuerzo en ser didácticos jeje , si algunos NP completos son fáciles de enunciar , estaría genial que los nombraseis en algún futuro vídeo, like y os comparto.
Pero que buenos videos este canal, lastima no haberlo conocido antes (y lastima tambien la introduccion a los videos jaajjajja bromeo). Felicidades, excelente trabajo!
He leído muchos de los comentarios y también me ha agradado que respondas a las preguntas o dudas. En mi caso pregunto, si p resuelve (ecuación polinomial ) y pn (ecuación exponencial )comprueba dicha solución entonces, ¿lo que se busca es que pn sea polinomial?
Parece ser que faltó la aclaración de que se refiere a una solución óptima (no solo factible) del problema: si tengo tres mil canciones y quiero calcular cuántos discos necesito con garantía de grabarlas todas, basta con usar tres mil discos, eso es una solución factible y hasta grabarlos se hace en un tiempo razonable, la dificultad yace en cuál es la solución que MINIMIZA el número de cds. Sin temor a equivocarme: problema P si hay algoritmo polinomial para encontrar solución óptima, NP si hay algoritmo polinomial para comprobar si una solución es factible aunque no necesariamente óptima. Me gustaría ver un video donde se explique más a fondo NP-completos y también el tipo NP-Hard, me suscribo, saludos
Ya veo porque es tan difícil de resolver porque se necesitaría comprobar una cantidad de cosas increíbles ya que la respuesta depende de su decisión entonces si en una ha como 5 posibilidades tendría que verificar y resolver correcta mente. (yo pienso que P=NP ya que no se puede tener algo si no hay algo que lo provoque pero la respuesta se la dejo a otro que se le de bien la matemática y la analítica ya que seria una perdida de tiempo para conseguir una respuesta yo simplemente vería el problema y buscaría la solución por la que se me facilite mas con el problema) (pero lo mas probable que se allá resuelto pero se allá ignorado ya que lo mas probable es que sea P=PN y están esperando a alguien que encuentre o cree la línea en que P no es igual a NP esto es complicado ya que si revisas las respuestas que hay hoy en día llegas a la misma conclusión entonces tienes que seguir hasta que no Allan mas opciones y tratar de encontrar la respuesta que se quiere y esto es posible pero seria una pérdida de tiempo excepto que sea dividido y se pueda simplificar las soluciones por tiempo y persona y así acelerar el proceso pero mientras tanto yo redondeo que se necesitaría unos 300 o 500 años de trabajo sin pausa y sin fallos.(creo).( igual creo que resolverlo no tengo el nivel matemático aun talvez cuando sala de la escuela me pueda especializar en esto y logra resolverlo con la respuesta que se desea pero mejor lo dejo para mi futuro y me esfuerzo en seguir dominando todas las reglas matemáticas que se hasta hoy edad que tengo una edad de alguien joven y prepararme para las que me faltan por aprender).
ya entiendo mucho mejor la relacion de p y np, muy buena la explicacion, gracias que chevere.
7 ปีที่แล้ว
Yo hice los cálculos del problema del ajedrez y el arroz... No digo dónde está para evitar que me acuséis de spamer jejejeje... Pero en google se puede encontrar. Y por cierto... Está genial explicado y el ejemplo final es muy aclaratorio.
Cordial saludo profesores... les comparto que solicite a varias entidades la revision del problema P versus NP y me lleve tremenda sorpresa!!... todos ellos me piden que les seda mis derechos de autor... tremendo, me gustaria poder contar con su apoyo para contactar al Instituto Clay de Matematicas para enviarles el proyecto para su revision. Gracias
Los problemas de decisión son problemas de optimizacion. En el entendido de que un problema de decisión seria solo poder demostrar que sí existe una (única) solución o que algo en especifico es (o No) una solución; sin embargo un problema de decisión seria mas que eso, ya había que caracterizar como son todas las soluciones si es que hubiera mas de una, o en definitiva demostrar que algo en específico NO es solución, sino que además en definitiva NO hay soluciones de cierto tipo o de ningún tipo. Hasta allí es correcto. Y hasta se puede tolerar afirmar que los problemas P son básicamente de decisión, y los NP son de optimización . Sin embargo, siendo más técnico, los problemas tipo P, son aquellos que es posible resolverlos o proponer una solución aproximada ( según cierto criterio) mediante un procedimiento o algoritmo determinístico y su complejidad es polinomial. Y los problemas tipo NP, son aquellos que es posible resolverlos o proponer una solución aproximada mediante un procedimiento o algoritmo NO determinístico y su complejidad sigue siendo polinomial. En otras palabras, es claro que los problemas que admiten solución determinística polinomial, se pueden resolver de modo no deterministico polinomial, pero al reves quien sabe!. Por lado hay problemas que son deterministicos con complejidad NO polinomial, y otro NO determinísticos con complejidad NO polinomial. A nadie le interesan los problemas de complejidad NO polinomial, ya que NUNCA habria tiempo suficiente para resolverlo, conforme el problema se complique al crecer tu tamaño, asi haya un algoritmo o procedimiento determinístico o No Determnístico con el cual en teoría seria posible resolverlo.
Un punto tiene y no tiene una ubicación es espacial a diferencia de un numero que es una representación de una cantidad un punto puede representar el espacio y sobre ese espacio ubicarse todos los NP y en otro punto todos los P y hacemos lo mismo con el tiempo considerándolo otro tipo de espacio que sucede entonces...
Si existe un algoritmo para saber cuantos cds se necesitan, y muy facil de saber , ordenas las canciones por duracion y divides el tiempo por la capacidad del cd. Y asi obtienes los numeros de cd que necesitas. Algo mas?
@EDUARDO SAAVEDRA SE PUEDE HACER EL ALGORITMO Y ES BASTANTE SENCILLO , SE HACEN GRUPOS DE CANCIONES DEPENDIENDO DE SU DURACIÓN. Y SE DIVIDE EL EL TOTAL DE CADA GRUPO POR LA CANTIDAD DE ALMACENAMIENTO DE CADA CD Y ASI OBTEMOA CUANDO CD OCUPAMOS.
Pero se trata de no cortar las canciones y no desperdiciar la capacidad de los discos. Un algoritmo que cuente las canciones y devuelva esa cantidad (una canción por disco) sería de O(n), aún más rápido que tu algoritmo je je.
@@manuelmb7256 SI , AUNQUE EL ALGORITMO QUE PROPUSE LO HICE DE MANERA DE EJEMPLO DE QUE SI PUEDE REALIZAR UN ALGORITMO PARA DETERMINAR EL NUMERO DE CD'S.
Hola. Primero, saludos y felicitaciones por el video. Excelente. Sin embargo, no entendí lo dicho en el siguiente tiempo del video: 11:32 - 11:53. ¿Podrían explicar ese dicho con ejemplos?
Se trataría de encontrar un problema que se sepa que está en NP para el que se pueda demostrar que ningún algoritmo polinomial encuentra una solución para el problema. Por ejemplo, si alguien demuestra que el problema de encontrar el mayor número de vértices independientes (sin aristas entre ellos) de un grafo, no se puede resolver con un algoritmo polinomial, habría demostrado que P es distinto de NP.
Gracias por responder, Alberto. Ahora, con la intención de ir más allá de solo comprender esto, ¿cuáles son los problemas que están en NP que se deben demostrar que no se pueden, o que sí se pueden, resolver con un algoritmo polinomial, es decir, qué problemas que están en NP hay que demostrar que su P es distinto?
Hola Alberto. Dándole vueltas al tema se me han ocurrido una serie de preguntas.... - Si alguien pudiera demostrar que P = PN, se habrá resuelto un problema, (el que sea que ahora es inviable), imaginemos que ha resuelto el problema del viajante y tiene su algoritmo. Pero por ejemplo si alguien quiere factorizar un numero muy grande. Como es lógico... ¿Tiene que buscar el algoritmo en concreto, el que resuelve la factorización?. En otras palabras, alguien puede revolver P = PN, pero hay que buscar los diversos algoritmos. -Cuando la computación cuántica se desarrolle... ¿Entonces todos los problemas se revolverian en un tiempo razonable y entonces P = PN?. -¿Que tipo de complejidad tiene el problema de factorizar un numero muy grande, es NP-completo?. Muchas Gracias...
Hola, primero que todo muy buena explicación!! Una duda solo tengo: por qué el problema de los CDs sería NP? tiene algún nombre ese problema? para buscar referencias
Hola, el video esta muy bien, pero si se considera que el problema del viajante (TSP) es un NP-completo, y Karaboga fue capaz de resolverlo aplicando los algoritmos basados en colonias de hormigas (ACO) NP seria igual que P???
Ainhoa Vasco no exactamente, la heurística de colonias de hormigas (así como otras basadas en algoritmos genéticos), no dan una solución exacta de forma determinista, sino que da una solución aproximada a la óptima, sin poder garantizar que ésta se alcance.
.... O lo que entiendo al final es que UNA COSA es demostrar que el problema se puede resolver mediante un algoritmo que utilice un tiempo polinomial para resolverlo Y OTRA DISTINTA encontrar el algoritmo en cuestión.
No exactamente, aunque esa es una cuestión interesantísima (y mucho más difícil), la diferencia entre P y NP es que P resuelve el problema y NP comprueba que algo es solución del problema (ambos en tiempo polinomial).
Tengo una duda: Tú hablas de "número polinomial de operaciones", sin embargo yo he leído que de lo que se trata es que el tiempo de ejecución esté acotado por un polinomio, es decir: "tiempo polinomial", no es lo mismo no?.
hola chanchitos. En el video comentáis que si alguien demuestra que P es distinto de NP le dan 1 millón de $. Pero si fueran iguales no le dan nada?. El problema no quedaría. resuelto?.
Jose Brihuega tal y como se conoce habitualmente es de otra clase llamada NP-duro, pero se puede dar una versión NP-completa, basta con añadir un k en el enunciado y preguntar si existe un recorrido de longitud menor que k.
N=NP y NP=N por la ley de causa y efecto y todos los resultados son comprobables. La formula para resolver se basa en la cantidad de letras y/o números como respuesta o como problema. Me gustaría saber donde esta el link de esa escuela para darles la formula general. y si quieren que N no sea igual a NP no aplica en informática ni matemáticas este aplica al tiempo y espacio.
lo de los cds supongo que es para dar un ejemplo ya que si vos sabes que un cd que lleva 80 minutos, y tenes 1500 canciones, solo debes buscar canciones que conlleve a ocupar esos 80 minutos completos. si queres saber cuantos discos queres necesitar, solamente medis todos los minutos de todas las canciones, osea los sumas, en base a eso supongamos que te da no sé, 4500 minutos, a 80 minutos por disco, sabes que necesitas 57 discos y el ultimo le resta unos 60 minutos. osea para 1500 canciones de 3 minutos cada una de las canciones te llevaria 57 discos. si cada disco tardara 1 hora (por ejemplo) en quemarse, porque en principio 80 minutos son 80 minutos, 57 discos tardará 56 horas 20 minutos en terminarse.
No, no es eso, cada canción dura un tiempo distinto y no sabes si meter una canción larga en un cd que cabe pero que dejaría poco espacio o pasar esa a otro cd y grabar en el antiguo dos canciones en el espacio restante. Es el problema conocido como bin-packing y si lo sabes resolver eficientemente tienes un premio de un millón de dolares.
Creo que la respuesta es que P=NP. La cosa es tan simple como demostrar que para cada k existe un z que satisfaga k^n=n^z. Ahora sin duda la cantidad de digitos de z es proporcional al valor de k por lo que no hay ningun tiempo razonable 😂😂
Una pregunta si doy un problema de hallar la distancia exacta en centímetros desde la punta de mi dedo hasta el borde mas cercano de la luna, doy mi posición exacta hora momento donde estoy, y de alguna forma el tiempo se detiene y se pueda medir exactamente esa distancia no seria un problema P? y NP? a la vez? o sea se mide la distancia fácil, pero en tiempo real se demoraría pero se le puede dar una solución. un problema NP deja de serlo cuando se tiene la respuesta?, yo se que NPvsP se refiere a la complejidad por eso hice un problema relativamente fácil una suma. Que es broma todo xd no se ni lo que digo buen vídeo.
una cosa es que consiga resolver NP-Completos y otra es que despues de eso me secuestren y me obligue a armar un algoritmo que encuentre los numeros primos que se utilizan en internet 🤣
no entendi cual es el problema, no se sabe pudo comprobar q n sea igual a np, o no se pudo comprobar q son distintos? y si es asi, entonces a kien se le ocurrio esta ecuacion si ni sikiera saben una respuesta? yo podria inventar una y les dejaria a todo el mundo pensando si gato es igual a gato x, o distinto, y asi estariamos boludeando con ecuaciones sin sentido por siempre, q sentido tiene crear algo q ni los q lo crearon saben q es? o por ahi no entendi una mierda y estoy hablando al pedo xD
Se llaman conjeturas/hipótesis y son muy interesantes. De que sirve plantear un problema si no uedes hallar la solución? Pues te da mucha información de lo que sabemos y una vez resuelto el problema (si es resoluble) es de mucha ayuda en muchos campos científicos, computación, manejo de la información, etc.
Lo gracioso es que esa ecuacion que darias seria probada falsa muy facilmente xD. Lo que tenemos es una conjetura. Una proposicion que no se dabe si es verdadera o falsa. Precisamente el problema es demostrar cual de las dos es. La gente si sabe que es el conunto PN y el conjunto P. El asunto es demostrar que son iguales. En conjuntos tu dices que A=B. Si desmuestras que todo elemento de A pertenece a B. Y todo elemento de B pertenece a A. Demostrar lo contrario podria ser demostrando que existe un elemento que pertenece a uno y no al otro.
Clases de complejidad P y NP La relación entre las clases de complejidad NP y P es una pregunta por primera vez formulada por el científico computacional Stephen Cook que la teoría de la complejidad computacional aún no ha podido responder. En esencia, la pregunta ¿es P = NP completo?
Hace un par de meses quería crear un algoritmo para ayudar a mi padre con un problema de contabilidad, y gracias a su vídeo me doy cuenta que posiblemente era un NP-Completo, y que sin saberlo estaba buscando solución a uno de los problemas del milenio 😂, no lo continué por falta de tiempo, pero ahora, aunque ya no es necesario lo voy a intentar por diversión. Si lo resuelvo les dejo medio millón por la explicación 👌😂
puedes planterar tu problema- solucion :D
Y como te ha ido? xd
no responde, le deben de haber matado ya
y pues seguimos esperando pero ya son 2 años...creo que lo perdimos
Aquí seguimos esperándole
Pues es verdad, creo que es la primera vez que creo entender la diferencia entre P y NP
Hola un cordial saludo; he intentado presentar la solución a este problema matemático informático pero se me ha dificultado porque me piden seder mis derechos de autor. Que puedo hacer ? Se los agradecería. Mil gracias
Muy bien explicado! Después de 25 años, me he enterado de que van los problemas P y NP. Yo era de los que creían que los NP no eran computacionables y punto... Gracias.
NP viene de no-determinista polinomial (no determinista significa que no tenemos que determinar una solución, basta con comprobar que algo lo es).
Y se nos había olvidado el: "Muchas gracias".
Todo canal cultural que exponga problemas, merece su like y suscripción, un capo.
muy bueno el vídeo y la explicación. La sección de preguntas y respuestas tengo que decir que , aunque resulta muy interesante el ejemplo, me parece que dais dos veces la misma definición para problemas distintos y me acaba liando un poco.
Hola me pueden hacer el favor de regalarme le contacto para dar respuesta a este tema, llevo rato intentando comunicarme pero no me ha sido posible... Gracias
Gracias por aclarar un concepto que muchos se han encargado de nublar. Por cierto, los videos se renderizan (aún no reconocido por la RAE), los programas se compilan.
Buenas, ¿podrías explicar la diferencia enre NP Completo y NP Duro?. Gracias.
Cordial saludo señores Los 3 Chanchitos; Me gustaria saber si me pueden colaborara para contactar al Instituto Clay de Matematicas para revision de un problema matematico. Gracias
uy *Los 3 chanchitos* qué video tan espectacular!!!
Genial, gracias por el esfuerzo en ser didácticos jeje , si algunos NP completos son fáciles de enunciar , estaría genial que los nombraseis en algún futuro vídeo, like y os comparto.
Soy peruano, excelente video me ayudó muchísimo, gracias por compartir tus conocimientos :D
Muy buen video, muy didáctico. Se agradece.
Tengo una pregunta en que recae la dificultad ?
Os imagináis que alguien por la cara pone la respuesta al problema en los comentarios de este vídeo? Hubiese sido muy jocoso cuanto menos
Doort_01 le damos medio millón (y nos quedamos con el otro medio)
Muy interesante
lo del disco he entendio que n=pn pero ni suma resta o multiplicacion puede resolverse como determinamos el tiempo de cada disco
Pero que buenos videos este canal, lastima no haberlo conocido antes (y lastima tambien la introduccion a los videos jaajjajja bromeo). Felicidades, excelente trabajo!
Qué majo! Y me he reído además un montón.
He leído muchos de los comentarios y también me ha agradado que respondas a las preguntas o dudas. En mi caso pregunto, si p resuelve (ecuación polinomial ) y pn (ecuación exponencial )comprueba dicha solución entonces, ¿lo que se busca es que pn sea polinomial?
Parece ser que faltó la aclaración de que se refiere a una solución óptima (no solo factible) del problema: si tengo tres mil canciones y quiero calcular cuántos discos necesito con garantía de grabarlas todas, basta con usar tres mil discos, eso es una solución factible y hasta grabarlos se hace en un tiempo razonable, la dificultad yace en cuál es la solución que MINIMIZA el número de cds. Sin temor a equivocarme: problema P si hay algoritmo polinomial para encontrar solución óptima, NP si hay algoritmo polinomial para comprobar si una solución es factible aunque no necesariamente óptima.
Me gustaría ver un video donde se explique más a fondo NP-completos y también el tipo NP-Hard, me suscribo, saludos
Ya veo porque es tan difícil de resolver porque se necesitaría comprobar una cantidad de cosas increíbles ya que la respuesta depende de su decisión entonces si en una ha como 5 posibilidades tendría que verificar y resolver correcta mente. (yo pienso que P=NP ya que no se puede tener algo si no hay algo que lo provoque pero la respuesta se la dejo a otro que se le de bien la matemática y la analítica ya que seria una perdida de tiempo para conseguir una respuesta yo simplemente vería el problema y buscaría la solución por la que se me facilite mas con el problema) (pero lo mas probable que se allá resuelto pero se allá ignorado ya que lo mas probable es que sea P=PN y están esperando a alguien que encuentre o cree la línea en que P no es igual a NP esto es complicado ya que si revisas las respuestas que hay hoy en día llegas a la misma conclusión entonces tienes que seguir hasta que no Allan mas opciones y tratar de encontrar la respuesta que se quiere y esto es posible pero seria una pérdida de tiempo excepto que sea dividido y se pueda simplificar las soluciones por tiempo y persona y así acelerar el proceso pero mientras tanto yo redondeo que se necesitaría unos 300 o 500 años de trabajo sin pausa y sin fallos.(creo).( igual creo que resolverlo no tengo el nivel matemático aun talvez cuando sala de la escuela me pueda especializar en esto y logra resolverlo con la respuesta que se desea pero mejor lo dejo para mi futuro y me esfuerzo en seguir dominando todas las reglas matemáticas que se hasta hoy edad que tengo una edad de alguien joven y prepararme para las que me faltan por aprender).
Muy buena explicacion, quizas mejorar la explicacion del np completo y seria sublime
Excelente vídeo, me gustaría que colocaran paper donde poder leer mas del tema, no solo en este video sino en todos los que hagan.
Muy interesante, no voy ni por la mitad pero luego seguire viendo.
+1 Sub, saludos.
ya entiendo mucho mejor la relacion de p y np, muy buena la explicacion, gracias que chevere.
Yo hice los cálculos del problema del ajedrez y el arroz... No digo dónde está para evitar que me acuséis de spamer jejejeje... Pero en google se puede encontrar.
Y por cierto... Está genial explicado y el ejemplo final es muy aclaratorio.
Este es el único problema del milenio que puedo entender medianamente bien.
Cordial saludo profesores... les comparto que solicite a varias entidades la revision del problema P versus NP y me lleve tremenda sorpresa!!... todos ellos me piden que les seda mis derechos de autor... tremendo, me gustaria poder contar con su apoyo para contactar al Instituto Clay de Matematicas para enviarles el proyecto para su revision. Gracias
👏 excelente explicación
Like muy merecido
Br_ain_omo Muchas gracias
Los problemas de decisión son problemas de optimizacion. En el entendido de que un problema de decisión seria solo poder demostrar que sí existe una (única) solución o que algo en especifico es (o No) una solución; sin embargo un problema de decisión seria mas que eso, ya había que caracterizar como son todas las soluciones si es que hubiera mas de una, o en definitiva demostrar que algo en específico NO es solución, sino que además en definitiva NO hay soluciones de cierto tipo o de ningún tipo. Hasta allí es correcto. Y hasta se puede tolerar afirmar que los problemas P son básicamente de decisión, y los NP son de optimización . Sin embargo, siendo más técnico, los problemas tipo P, son aquellos que es posible resolverlos o proponer una solución aproximada ( según cierto criterio) mediante un procedimiento o algoritmo determinístico y su complejidad es polinomial. Y los problemas tipo NP, son aquellos que es posible resolverlos o proponer una solución aproximada mediante un procedimiento o algoritmo NO determinístico y su complejidad sigue siendo polinomial. En otras palabras, es claro que los problemas que admiten solución determinística polinomial, se pueden resolver de modo no deterministico polinomial, pero al reves quien sabe!.
Por lado hay problemas que son deterministicos con complejidad NO polinomial, y otro NO determinísticos con complejidad NO polinomial. A nadie le interesan los problemas de complejidad NO polinomial, ya que NUNCA habria tiempo suficiente para resolverlo, conforme el problema se complique al crecer tu tamaño, asi haya un algoritmo o procedimiento determinístico o No Determnístico con el cual en teoría seria posible resolverlo.
Un punto tiene y no tiene una ubicación es espacial a diferencia de un numero que es una representación de una cantidad un punto puede representar el espacio y sobre ese espacio ubicarse todos los NP y en otro punto todos los P y hacemos lo mismo con el tiempo considerándolo otro tipo de espacio que sucede entonces...
Hola Alberto. El vídeo genial, me ha encantado. Tienes pensado explicar que es un Calabi-Yau? Salen en la Teoria de Cuerdas.
Спасибо, доброе утро
Si existe un algoritmo para saber cuantos cds se necesitan, y muy facil de saber , ordenas las canciones por duracion y divides el tiempo por la capacidad del cd. Y asi obtienes los numeros de cd que necesitas. Algo mas?
¡Felicitaciones! No te olvides de cobrar tu millón de dólares.
@@MrGuillermolago GRACIAS
@EDUARDO SAAVEDRA SE PUEDE HACER EL ALGORITMO Y ES BASTANTE SENCILLO , SE HACEN GRUPOS DE CANCIONES DEPENDIENDO DE SU DURACIÓN. Y SE DIVIDE EL EL TOTAL DE CADA GRUPO POR LA CANTIDAD DE ALMACENAMIENTO DE CADA CD Y ASI OBTEMOA CUANDO CD OCUPAMOS.
Pero se trata de no cortar las canciones y no desperdiciar la capacidad de los discos.
Un algoritmo que cuente las canciones y devuelva esa cantidad (una canción por disco) sería de O(n), aún más rápido que tu algoritmo je je.
@@manuelmb7256 SI , AUNQUE EL ALGORITMO QUE PROPUSE LO HICE DE MANERA DE EJEMPLO DE QUE SI PUEDE REALIZAR UN ALGORITMO PARA DETERMINAR EL NUMERO DE CD'S.
Hola. Primero, saludos y felicitaciones por el video. Excelente. Sin embargo, no entendí lo dicho en el siguiente tiempo del video: 11:32 - 11:53. ¿Podrían explicar ese dicho con ejemplos?
Se trataría de encontrar un problema que se sepa que está en NP para el que se pueda demostrar que ningún algoritmo polinomial encuentra una solución para el problema. Por ejemplo, si alguien demuestra que el problema de encontrar el mayor número de vértices independientes (sin aristas entre ellos) de un grafo, no se puede resolver con un algoritmo polinomial, habría demostrado que P es distinto de NP.
Gracias por responder, Alberto. Ahora, con la intención de ir más allá de solo comprender esto, ¿cuáles son los problemas que están en NP que se deben demostrar que no se pueden, o que sí se pueden, resolver con un algoritmo polinomial, es decir, qué problemas que están en NP hay que demostrar que su P es distinto?
Hola Alberto.
Dándole vueltas al tema se me han ocurrido una serie de preguntas....
- Si alguien pudiera demostrar que P = PN, se habrá resuelto un problema, (el que sea que ahora es inviable), imaginemos que ha resuelto el problema del viajante y tiene su algoritmo. Pero por ejemplo si alguien quiere factorizar un numero muy grande. Como es lógico... ¿Tiene que buscar el algoritmo en concreto, el que resuelve la factorización?. En otras palabras, alguien puede revolver P = PN, pero hay que buscar los diversos algoritmos.
-Cuando la computación cuántica se desarrolle... ¿Entonces todos los problemas se revolverian en un tiempo razonable y entonces P = PN?.
-¿Que tipo de complejidad tiene el problema de factorizar un numero muy grande, es NP-completo?.
Muchas Gracias...
Si resuelves un NP completo haces una reducción al otro problema usando una función tal que f(x) se pueda resolver con el que ya resolviste, eso creo.
Hola, primero que todo muy buena explicación!!
Una duda solo tengo: por qué el problema de los CDs sería NP? tiene algún nombre ese problema? para buscar referencias
Supongo que te refieres a que el problema de los CDs es NP-completo. Es equivalente al problema del Bin-packing.
+Alberto Márquez, Muchas gracias!! :D
Hola, el video esta muy bien, pero si se considera que el problema del viajante (TSP) es un NP-completo, y Karaboga fue capaz de resolverlo aplicando los algoritmos basados en colonias de hormigas (ACO) NP seria igual que P???
Ainhoa Vasco no exactamente, la heurística de colonias de hormigas (así como otras basadas en algoritmos genéticos), no dan una solución exacta de forma determinista, sino que da una solución aproximada a la óptima, sin poder garantizar que ésta se alcance.
Ahh vale muchas gracias
.... O lo que entiendo al final es que UNA COSA es demostrar que el problema se puede resolver mediante un algoritmo que utilice un tiempo polinomial para resolverlo Y OTRA DISTINTA encontrar el algoritmo en cuestión.
No exactamente, aunque esa es una cuestión interesantísima (y mucho más difícil), la diferencia entre P y NP es que P resuelve el problema y NP comprueba que algo es solución del problema (ambos en tiempo polinomial).
Por fiiin alguien que explica el problema P=NP? !! de una forma claraa
Tengo una duda: Tú hablas de "número polinomial de operaciones", sin embargo yo he leído que de lo que se trata es que el tiempo de ejecución esté acotado por un polinomio, es decir: "tiempo polinomial", no es lo mismo no?.
Era tan facil y lo explicaban tan dificil, gracias
La solución de la conjetura de Collatz sería un problema P=NP?
Necesito su correo electrónico tengo posiblemente una solución
y yo.
muy buena explicacion
un verdadero video de terror. excelente
hola chanchitos.
En el video comentáis que si alguien demuestra que P es distinto de NP le dan 1 millón de $. Pero si fueran iguales no le dan nada?. El problema no quedaría. resuelto?.
Sí también le darían el millón de dolares, pero podría ser un grave problema.
La matemática es el idioma de los dioses
Jajajajajajjaja el final del video lo mejor
¿El problema del viajante es NP? Lo digo porque dada una solución no veo que sea muy fácil comprobarla.
Jose Brihuega tal y como se conoce habitualmente es de otra clase llamada NP-duro, pero se puede dar una versión NP-completa, basta con añadir un k en el enunciado y preguntar si existe un recorrido de longitud menor que k.
N=NP y NP=N por la ley de causa y efecto y todos los resultados son comprobables. La formula para resolver se basa en la cantidad de letras y/o números como respuesta o como problema. Me gustaría saber donde esta el link de esa escuela para darles la formula general. y si quieren que N no sea igual a NP no aplica en informática ni matemáticas este aplica al tiempo y espacio.
lo de los cds supongo que es para dar un ejemplo ya que si vos sabes que un cd que lleva 80 minutos, y tenes 1500 canciones, solo debes buscar canciones que conlleve a ocupar esos 80 minutos completos.
si queres saber cuantos discos queres necesitar, solamente medis todos los minutos de todas las canciones, osea los sumas, en base a eso supongamos que te da no sé, 4500 minutos, a 80 minutos por disco, sabes que necesitas 57 discos y el ultimo le resta unos 60 minutos.
osea para 1500 canciones de 3 minutos cada una de las canciones te llevaria 57 discos. si cada disco tardara 1 hora (por ejemplo) en quemarse, porque en principio 80 minutos son 80 minutos, 57 discos tardará 56 horas 20 minutos en terminarse.
No, no es eso, cada canción dura un tiempo distinto y no sabes si meter una canción larga en un cd que cabe pero que dejaría poco espacio o pasar esa a otro cd y grabar en el antiguo dos canciones en el espacio restante. Es el problema conocido como bin-packing y si lo sabes resolver eficientemente tienes un premio de un millón de dolares.
ah okey xd ya entendi e.e
más claro no puede ser
XD que buen video, entendí y me divertí, gracias. lml
Interesante la ciencia muy interesante
Yo he resuelto el problema, pero que se joda el mundo :P
Por qué le quitas el granito a 2^n? No le saques ese granito. Es muy importante.
Si tengo la solucion a quien le digo? O como lo comparto sin que me lo roben??
chanchitos expliquen los demás problemas del milenio porfavor :(
¿ el representar por completo el resultado de 70! Es una posible solución al problema P = NP o no ?
Creo que la respuesta es que P=NP. La cosa es tan simple como demostrar que para cada k existe un z que satisfaga k^n=n^z. Ahora sin duda la cantidad de digitos de z es proporcional al valor de k por lo que no hay ningun tiempo razonable 😂😂
Yo lo se, el problema es que si, P= NP
Porque? Porque sí.
Como me asusté al principio.
Todo un master
Que bien me lo he pasado
me gusta la cancion del chanchito
buenardo el video
Muy malo el volumen
Una pregunta si doy un problema de hallar la distancia exacta en centímetros desde la punta de mi dedo hasta el borde mas cercano de la luna, doy mi posición exacta hora momento donde estoy, y de alguna forma el tiempo se detiene y se pueda medir exactamente esa distancia no seria un problema P? y NP? a la vez? o sea se mide la distancia fácil, pero en tiempo real se demoraría pero se le puede dar una solución. un problema NP deja de serlo cuando se tiene la respuesta?, yo se que NPvsP se refiere a la complejidad por eso hice un problema relativamente fácil una suma. Que es broma todo xd no se ni lo que digo buen vídeo.
Gracias!!
No era arroz era trigo.
"no lo pasan del todo bien" jaja
😁😁😁😁🤣🤣🤣🤣🤣
una cosa es que consiga resolver NP-Completos y otra es que despues de eso me secuestren y me obligue a armar un algoritmo que encuentre los numeros primos que se utilizan en internet 🤣
Muy bajo el volumen del vídeo. Saludos.
Adoros los finales felices entonces si p=np los np dejarian de existir?
P VS NP solucion
no entendi cual es el problema, no se sabe pudo comprobar q n sea igual a np, o no se pudo comprobar q son distintos? y si es asi, entonces a kien se le ocurrio esta ecuacion si ni sikiera saben una respuesta? yo podria inventar una y les dejaria a todo el mundo pensando si gato es igual a gato x, o distinto, y asi estariamos boludeando con ecuaciones sin sentido por siempre, q sentido tiene crear algo q ni los q lo crearon saben q es? o por ahi no entendi una mierda y estoy hablando al pedo xD
Se llaman conjeturas/hipótesis y son muy interesantes. De que sirve plantear un problema si no uedes hallar la solución? Pues te da mucha información de lo que sabemos y una vez resuelto el problema (si es resoluble) es de mucha ayuda en muchos campos científicos, computación, manejo de la información, etc.
Lo gracioso es que esa ecuacion que darias seria probada falsa muy facilmente xD.
Lo que tenemos es una conjetura. Una proposicion que no se dabe si es verdadera o falsa. Precisamente el problema es demostrar cual de las dos es.
La gente si sabe que es el conunto PN y el conjunto P. El asunto es demostrar que son iguales.
En conjuntos tu dices que A=B.
Si desmuestras que todo elemento de A pertenece a B. Y todo elemento de B pertenece a A.
Demostrar lo contrario podria ser demostrando que existe un elemento que pertenece a uno y no al otro.
El premio es de 1 milon
quién daría la orden de ir por tu cabeza?
buen tema pero dilatado pero me aburrí , HAZLA MAS BREVE
Clases de complejidad P y NP
La relación entre las clases de complejidad NP y P es una pregunta por primera vez formulada por el científico computacional Stephen Cook que la teoría de la complejidad computacional aún no ha podido responder. En esencia, la pregunta ¿es P = NP completo?