What is the P versus NP problem?
Вставка
- Опубліковано 9 кві 2017
- In Derivando we face one of the seven millennium problems, or at least ... to explain what it is: What is the P versus NP problem? Go for it!
Subscribe to the channel!
Follow Eduardo Sáenz de Cabezon:
/ edusadeci
Follow us on Facebook:
DerivandoUA-cam
Explica todos los problemas del milenio
No puede si supiera crees que no los hibiera hecho hace años
@@nopedat2748 se refiere a explicar lo que se quiere resolver en esos problemas, no que los resuelva jajajajaja
Eso respondí yo en un examen de matemáticas de cuarto de la ESO.
No tenía tiempo para resolver el último problema, y escribí esto:
-El problema es demasiado complejo, por lo que no merece la pena invertir el tiempo necesario para resolverlo en hacerlo.
Al día siguiente el profesor (uno de los mejores que he tenido a lo largo de mi vida), nos explico de una forma similar lo que explicas en el vídeo.
Y bueno, a pesar de tener los otros 7 ejercicios bien resueltos, me hizo asistir a la recuperación (en la cual me deje de tonterías 😂)
usé las gemas para destruir las gemas
Espera, ¿el profesor te planteó el problema NP = P en un examen de 4to de la ESO?
@@user4241 ajajajajajahajajajaja
@@user4241 No entendiste xd
Cuando sacaste este video por primera vez me volava la cabeza pensar en que la ciencia podía ser tan interesante y así con muchos videos y problemas que presentabas, me imaginaba en que situaciones se estudia eso, hasta que llegué a la universidad y me tocó ver y analizar estos problemas de primera mano, gracias por los vídeos que me hicieron tener esa curiosidad y amor por la ciencia. Ahora me encuentro a la mitad de mi carrea en ciencias de la computación y espero algún día poder aportar mi granito de arena a esta gran comunidad
Excelente! Para los que piden videos más seguido, si eso implica que disminuya la calidad de su contenido prefiero esperar lo que sea necesario.
por favor, haz un video por cada problema del milenio !
POR FAVOOOOOOOOOOOOOOOOOOOOOOOOOOR
@@patitoybarra6275 Los está haciendo el canal MatesMike
Impresionante la capacidad para explicar a los profanos la matemática de este nivel. Mil gracias y siga trabajando desinteresadamente por nuestra educación.
NP es "no presentó" y es la calificación que te ponen en mi escuela si no asistes a clase XD
Yo saque eso es mi boleta, como que no significa "Niño Prodigio"?
@Jesús Gabriel Salas Ramirez jajajaja igual a mí
Un huelum o que?
Necromatuújajaja
@ElPolloRosa aguante el corte espacialhermnekekeke
Por un momento al leer el título pensaba que ibas a explicarlo con máquinas de Turing y no se me ocurría una forma fácil de hacerlo sin introducir muchas definiciones, la verdad.
Me encanta que hayas conseguido explicación correcta y relativamente corta y sencilla para esto porque mucha gente se entera de lo del "problema de un millón de dólares" y luego al buscarlo por ahí no se entiende o contiene muchas inexactitudes.
Gracias por hablar más acerca de la computación! Muy pocas personas se atreven a hablar de un tema tan poco "comercial" como lo es esta ciencia. Recuerdo que hace unos videos comenté que por favor hicieran un video acerca de esta area, continúen con ese gran trabajo :D Toma tu like buen señor
Brutal!! Más vídeos de los problemas del milenio!!! Al menos los que puedan explicarse por encima como en este caso :D
estuve toda la ESO sacando 5 en matematicas y el verano pasado encontre ti canal y me interese por las mates gracias a tus videos y ahora estoy sacando 9/10 en todos los examenes, grx edu
¡Justo ayer estaba mirando esto en Wikipedia (por encima) y no entendía nada! Qué guay que lo expliques aquí :D
Otro video fenomenal. Muchos de los suscriptores imploramos videos más frecuentemente, ¡por favor!
Precioso video Edu!!! Aqui va una frase que me encanta de Scott Aaronson (un gran matemático-informatico) sobre el problema P-NP
"Si P = NP, el mundo sería un lugar muy distinto al que solía ser. La creatividad no tendría un valor especial, no habría diferencia sustancial entre resolver un problema y reconocer una solución. Todo el que supiera apreciar una melodía sería Mozart, y todo el que pudiera seguir una argumentación matemática sería Gauss..."
Bueeeno a ver, eso no se traduciría siempre al mundo físico
Además p=np significa que tanto la solución como la resolución son *polinomicas* pero la solución podría ser x^2 y la resolución x^1000000000, es decir que seguiría siendo difícil y por lo tanto diferente
Si exageras y simplificas un problema (lo que Scott tuvo que hacer para dirigirse al público) la respuesta puede ser una extrapolacion dedcabellada
Bueno, quizá así el autoestima de la gente se eleve y la barrera de lo posible o lo imposible ya no sería posible de distinguir.
De esta forma, las personas no tendrían límites y al no tener límites llegaríamos al límite real de lo que el ser humano pueda llegar a realizar :V
@@sebastiansanchezgarcia477 Ajá ahora en español
@@mattromo2220 eh grfycrdwd hhggffguct
Emmm NOP.
El hecho de demostrar que existe una solución de baja complejidad no significa que sea fácil de encontrar. Ejemplo: el teorema fundamental de la aritmética nos garantiza que todo número natural mayor que 1 tiene una descomposición única en factores primos salvo el orden de los factores. Osea que con cualquiera de esos números sabemos que la factorización en primos existe, pero muchas veces es muy difícil de encontrar.
Este canal está de lo mejor. muy buen contenido!
Eduardo, siempre reviso tus vídeos!! Eres un grande!
¡Parece que me lees la mente! Hace unos días estaba aprendiendo sobre algoritmos y Big O, y en el vídeo hablas sobre heapsort, bubblesort, etc :O
Excelente explicación.
Excelente explicación muy buen vídeo. ¡la complejidad de un problema es el mejor algoritmo que lo resuelva¡
Esperaba con ansias que hicieras este vídeo. 🙂
podrías explicar la conjetura de Poincaré y su solución planteada por Grigori Perelman?
amo a este hombre 😂
Has vuelto a despertar mi nerd interior. Son geniales tus explicaciones, lo que ya entendia lo entiendo mejor, y lo que no, me deja curioso y voy por mas...
No dejes de crear contenido porfavor ! Este es uno de los mejores canales de ciencia. Muy pero muy bueno, muchas gracias. Saludos!
Tengo 13 años, las mates del insti son demasiado lentas. Tu canal mola mucho, debería conocerse más
Yo lo veo hace un año y siento lo mismo. Esperate a tener unos 16 o 17, se va poniendo interesante :)
Tengo 9 años y creo que los que comentan estas cosas y tienen de 10 años para arriba son un chiste
Pablo Perez Aparicio y deberían durar mas
Hombre es que si le ponen mates difíciles a un chaval de 13 años se va a agobiar.... Yo me acuerdo que era raro cuando en esa época no sacaba un excelente alto de mates... Y ahora con 17 años ya la cosa no es tan fácil.
Yo aún no nazco y soy tan inteligente que el problema N=NP es trivial
Derivandoo!! Has algun video sobre el cubo rubik que en alguno de tus videos dices lo armas en 7 segundos! Jajajajaj! Excelente tus videos
Estudio programación y este es uno de los temas mas interesantes de mi carrera
Gracias por el video Maestro
excelente explicación!
Todo un mes esperando que subieras video! Gracias, aunque molaria mas que subieses videos mas seguido! 😉
La primera vez que escuché hablar de este problema fue en la serie NUMB3RS, en la que el prota matemático se encierra en su estudio durante horas y días para intentar solucionarlo. Me pareció interesante e investigué al respecto pero no llegué a entenderlo muy bien. Muchas gracias, Edu, ahora lo he comprendido un poco mejor y creo que ya puedo empezar a resolverlo! :P
Ya lo resolviste?
Y terminaste?
La P es problem y su solución es NP que es el No Problem :v
xD
Te la matematicamamaste
La respuesta a todos los misterios del Universo :v
Tengo un PN enorme
mcmti7 mcmti7 encerio?
Explicas bastante bien. Hace unos minutos vi ese problema y no entendía pero ahora que encontré tu vídeo lo entendí muy bien :)
me flipa lo didacticos que son tus videos, enhorabuena¡¡
PNP es un tipo de transistor.
;)
jajajaja
NPN :)
Tharteon sí, ese es el otro tipo de transistor
el sándwich de los procesadores
Elque tefaka eso es P&P
Suba videos más seguido por favor :)
Muy buena tu explicacion, realmente tiene mucha importancia el tema, y mas en problemas de optimizacion combinatoria donde por problemas de complejidad hay que usar tecnicas de IA para dar respuesta en un tiempo razomable de espera y encontrar soluciones optimales o en el mejor de los caso lo suficientemente buena como para satisfacer nuestros requisitos, recuerdo mis tiempos de la uni diseño y analisis de algoritmos y modelos de optimizacion, matematica numerica y ufff muchas asignaturas, saludos
Tengo un examen mañana de algorítmos y complejidad; y me has hecho entender en 6 minutos lo que el profesor no ha conseguido en horas de clase :) muchas gracias, has sido de mucha ayuda.
Es hora de tratar la función de Riemann en este canal, por aquí lo dejo.
PD: Muy buena explicación, como siempre. Sencilla y para todos los públicos.
Especial de Maryam Mirzakhani
Excelente, muy bien explicado! Me suscribí :D
Lo que daría yo por un video semanal de este canal...
hola... excelente sigue así
saludos desde Perú 🌎
Romer Alcon Perez pues dificil que un biliviano haya entendido xdd
Un boliviano arrogante? creo que ya viene el fin del mundo jajajajjaa
Eres muy "inteligente" para no darte cuenta de la burla, jajajajja
Rabi c boliviano promedio
Romer Alcon Perez admirable :D
Que grande sobre todo el final xd
Gracias por un video tan largo! Se nota que te ha costado mucho, y una gran cantidad de edición. Espero puedas traer mas videos asi :D
Esto de la ordenación siempre me a gustado empezando con las permutaciones.
No sé ni por qué miro estos videos si la mayoría ni los entiendo :'v
Sigue viendolos y poco a poco tendrás base para ir entendiendolos. Tambien puedes darte un paseo por los infinitos blogs que tratan estos temas...
te entiendo, de hecho en casa me preguntan eso mismo xD
Será porque tu capacidad cerebral no te da
@@jabujavi no
@@user-dn6sl5gx8l eso es neurologicamente imposible.
A mi esto me resultó fácil de entenderlo, cuando en un programa de mi propia autoría conseguía que resolviera estructuras (tipo emparrillado), y cuando estas eran pequeñas (4×4 por ejemplo), se resolvían rápido, cuando eran de 10×10... ya era otra cosa y el consumo de RAM también se disparaba.
Qué buen video, muchas gracias.
Gracias señor Lenin matemático, muy interesante su video
Amigo eres el Heroe de las matemáticas
PNP: POLICIA NACIONAL DEL PERÚ :"v
Ste men
Alejandro , eso es el tercer comentario que te pillo insultando a los grasosos , yo tengo la idea si algo no te gusta no gastes tiempo , igual que yo ahora :'n
Postata: no lo digo por defender a los grasosos ni a nadie....
Estaba pensando en eso xddd
Es un simple comentario, ni ha mencionado nada vulgar y tirais de grasoso si que se les va la flapa
Me encantan tus videos, y siento envidia sana
... felicidades
Como todos EXCELENTES #Derivando
saludos! soy u fan :3 xd
Como curiosidad este es el problema que Charlie en la serie Numbers (serie policiaca que usa las matemáticas) se pone a intentar resolver cada vez que le pasa algo serio y se encierra en sí mismo, que yo sepa nunca lo "resolvió" pero no he visto todas las temporadas jajaj
como curiosidad tmb aparece en la serie ELEMENTARY
excelente explicación gracias!!
me encanta este canal!
P=NP
P=N*P
N=P/P
N=1
Listo, ¿dónde esta mi premio?
No podés pasar dividiendo porque no se puede dividir por cero.
Lo correcto es 0=(N*P)-P =(N-1)*P
En ningún momento ha dividido por cero... de hecho, lo que tú pones da el mismo resultado.
Pero tampoco a considerado la posibilidad de que P sea cero.
x=2x ... intenta resolverlo, Nelson ;)
(N-1)*P tiene infinitas soluciones si N y P son matrices.
Rafael Mendoza jajajaja
lo estoy viendo alas 6 am
Sería genial que hicieras videos con los otros problemas del milenio, especialmente acerca de las ecuaciones de Navier-Stokes!
Excelente explicación 🎉
No se como haces para que me entere de esta clase de cosas mas fácilmente que la simple teoría de Matemáticas
Davidbelesp bueno, ahora anda y lee la formula y hacemos un ejercicio te parece? 😅
¿Hablarías de la teoría de los juegos?
lo haré :)
teoria de truelos y n-uelos
Listo, ya lo hizo xd
Excelente vídeo!!!! Saludos ,♥
Muchas felicidades, si nuestros docentes tendrían tu estilo de explicar este mundo sería muy distinto, sigue adelante que tienes un público con ganas de aprender ......... podrías hacer vídeos de los 7 problemas del milenio? ...... Saludos
Buena explicación muchas gracias!, por curiosidad cuales funciones crecen mas rápido que las funciones exponenciales , por ejemplo tengo entendido que la función delta de dirac es mas rápida, pero que otras crecen mas rápido que una exponencial, gracias de antemano y saludos desde Venezuela me parecen excelentes tus vídeos.
Mírate la función de Ackerman, vas a flipar.
n! crece mucho más que 2^n. En términos computacionales se podría decir también que 2^(2n) crece mucho más que 2^n también, puesto que hay problemas que se pueden resolver en tiempo 2^(2n) pero no en 2^n.
Gracias por sus respuestas, me apasionan las matemáticas puesto que en realidad es de lo que esta hecho nuestro propio mundo.
Cosh x tampoco se queda corto
Excelente vidéo!
Hay algo que me gustaria saber:
Si entendi bien, resolver el problema del viajero (por ejemplo), demostraria que p es igual a np?
Cual seria una forma concreta de probar que son diferentes?
Y mejor aun, que seria necesario para probrar que no es posible afirmar si n y np son o no iguales?
Te respondo 3 años después de que plantees la pregunta (aunque no 3 años después de conocer la respuesta a la misma...)
No, resolver el problema del viajero no demostraría que P=NP. El problema del viajero, al igual que el de las N Reinas (N siendo un entero positivo) u otros del mismo estilo no son más que acertijos, problemas que tienen solución y varias formas de solucionarlos.
No tengo tantos conocimientos como para saber una forma concreta de probarlo, pero sí te puedo decir que yo intentaría buscar un contraejemplo. Es decir, buscaría una solución a un problema NP que no se pueda resolver, es decir, que no esté en P.
@@jorgemorenomartinez2632 creo hay algo de confusión en los conceptos y te cito textualmente, "buscaría una solución a un problema NP que no se pueda resolver, es decir, que no esté en P", eso es justamente el problema de si P=NP porque no se sabe si NP está o no en P (no puedes decir que un problema es exclusivamente NP hasta no encontrar un algoritmo en P que lo resuelva). De hecho solucionar un problema NP en el que hasta el momento no exista un algoritmo en P que lo resuelva no es demostración, ya que eso se ha hecho para instancias de problemas NP pequeños, el agente viajero por ejemplo (y en general casi todos los problemas combinatorios). Lo que sí sería una demostración y se menciona en el video sería encontrar un algoritmo en P que resuelva un problema NP completo, con eso bastaría y te llevarías el millón de dolares (y la gloria eterna). Pero para eso tendríamos que entender que es un problema NP completo, un problema NP completo es un problema NP que es "reducible" a otro problema NP y por reducible me refiero a que puedes encontrar una función que permita plantear un problema NP como otro problema NP, por ejemplo, plantear un problema del agente viajero como un problema de encontrar el número de triángulos en un gráfo (o viceversa), resuelves "x" problema como si fuera "y" problema y luego "reduces" la solución a su planteamiento original (algo así como una transformada por decirlo de algún modo). El asunto es que todos los problemas NP completos son reducibles entre sí y específicamente al problema del 3-SAT o el llamado "problema de satisfacibilidad booleana de la forma normal conjuntiva 3" y es que, todos los NP completos son reducibles a este problema NP, si alguien encontrara un algoritmo que resolviera este problema (3-SAT) en P, ya resolvería todos los NP y por añadidura demostraría que NP está en P, el detalle es que nadie ha encontrado dicho algoritmo (Nota adicional, existen problemas peores que los NP completos y son los NP duros, esos problemas no se pueden resolver en P y tampoco se pueden verificar en P, son una cosa asquerosa).
Probar que p y np no son iguales bastaría con demostrar que no existe un algoritmo que resuelva "x" problema en tiempo p. Con un sólo problema que estemos seguros que no se puede resolver en tiempo p, con eso bastaría para decir que p es dintinto de np. El problema es que asegurar que no existe ningún algoritmo que resuelva un problrema np en tiempo p es a mi punto de vista, igual o más difícil que lo contrario, es decir, demostrar de forma generalizada que todos los problemas np tienen al menos un algoritmo que los resuelva en tiempo P.
@@jorgemorenomartinez2632 Te respondo 1 año después de tu respuesta, no son acertijos, son problemas matemáticos con múltiples escenarios, tanto correctos como incorrectos, si bien es cierto que tienen varias formas de solucionarlos, no significa que no puedan pertenecer a la clase de NP completos, ya que, como se plantea, no se busca solamente una solución, sino una solución en tiempo polinómico. El problema del viajante a partir de 13 ciudades con costos síncronos tiene una cantidad enorme de operaciones que las computadoras tardarían horas o días en solucionarlos, eso si no se agota la memoria antes de llegar a la solución. El problema de las 1000 reinas tienen 1000^1000 escenarios, saber cuantos de ellos son correctos es ya de por si difícil, se vuelve aun más complicado con la regla de que algunas reinas ya están ubicadas en ciertos lugares. Ninguna computadora actualmente puede resolver ninguno de los dos problemas ya mencionados con tiempo polinomial, es por esto que se vuelven parte de NP-Completos
Flaco, soy apenas un diletante poco dotado. Me encantan tus videos.
Justo te iba a preguntar sobre estos problemas.
te faltó decir que el problema está apartado para que yo sea el que lo resuelva, tan solo esperemos a que llegue la computación cuántica :)
PD: ¡¡¡sigo esperando un vidrio de la teoría del caos!!!
Lo resolviese? :u
si subieras vídeos más seguidos crecerías muchísimo
Al fin entendí este tema, gracias!!
Me gustó tu video, muy bien explicado ya me suscribí
que curioso justo como mi nombre
Alguien notó el fondo musical de la ambientación de violetta min 3:10
Me encantó este video dé verdad
Me encanta tu canal esta lleno de datos, soluciones y demas, me encanta
Hola! He estado trabajando en este problema recientemente, y creo que me he acercado mucho a su solución, pero como no soy profesional (sino autodidacta) no se si estoy yendo por el camino apropiado. ¿me mandarías tu gmail o el de algún profesional para que me ilustre un poco el tema?
Muchas gracias.
Si no me equivoco, su correo es
info@tuiwokestudios.com
. Suerte.
@@ramonparelladamartin4877 gracias 👍
Y decía al principio del video que lo resolvería de manera sencilla
Está muy bueno este video, pareciera que es hasta cultura general, pero si eres programador y piensas aplicar para una empresa como Google necesitas saber de estás cosas.
Sos un grande man estudio ingeniería informática y no hay mejor manera para explicar
no entendí nada :u
profesor son fantasticas sus explicaciones lo malo es que como buen español cuesta agarrarle el ritmo pero es buen pedagogo,me gustaria su explicacion sobre las ecuaciones fractales.gracias
desde el 2010 intentando entender que quiere decir este problema y por fin me lo explican claramente
gracias por el video muy bueno
No entendí casi nada :'(
Y yo que quería hacer el tecnológico...
Muy buen vídeo Eduardo, sigue así, esperamos más contenido con ansias!
Haz un video sobre las Ecuaciones de Navier-Stokes!! Creo que es otro de los problemas del milenio
Hola
¿Qué tal?
Deus Bien y tu?
Deus Me cago en Dios, me pongo muy nervioso con los "¿Qué tal?" :"c
¿Quien lo tuvo que ver unas 3 veces o más? :'V
Lo hago por placer :v
Wow la primera vez que vi este video en este canal me acuerdo que no entendi ni peter, 1 año dps y habiendo aprendido a programar por fin entiendo de que trata el probelama
Gracias,buen video
P=Primo
N=Número
P=7
N=1
7.1=7
Yo quiero estudiar Ciencias de la Computación :)
jajajaj te deseo suerte
y mucha matemática amigo
Me encantan tus videos 😂 soy de los primeros en ver este video 😂😂😂saludos desde México 🇲🇽
Muchisimas gracias Eduuuu!!
(Mostraré el video en mis clases por si no te importa)
En el colegio me decian "P NP" yo decia "¿Que?" y ellos decian "ño"
=(
¿Eres profesor verdad? Si es así ¿De donde?
En la Universidad de La Rioja
Edu Sadeci Mierda, no puede ser mi profesor.
Edu Sadeci de la Rioja Argentina :D ? ahre boludo.. jajaja ojalá...
Es matemático de carrera y profesión.
De verdad crees que un profesor podría explicar tan bien? :v
DIOSSS AMO TU VIDEO
Genial ya había leído de los problemas