Fe de errores: el problema de las N-damas no es NP-Completo, pero sí lo es si antes hay algunas damas sobre el tablero. Aquí tenéis el link al paper: t.co/mk0NvGT8KZ Mil gracias a @CarlosMarah por darse cuenta :)
Hay problemas NP completos muchísimo más sencillos de entender e investigar como el Subset Sum Problem. Siempre me ha parecido curioso que se le dé más importancia a problemas como la hipótesis de Riemann , cuya resolución no aportaría nada nuevo (excepto las mates y el enfoque que traiga la propia demostración), que el problema PvsNP , la cual, de ser cierta, sería un impulso brutal en computación científica, en logística, en transportes..etc.
Te lo tomas a broma pero eso lo más cerca que nadie estará jamás de la respuesta, sino el día que alguien encuentre el más complejo de todos los problemas P y que simultaneamente sea el menos complejo de todos los problemas NP también lo resolverá.
Jaja :d. No pues p=np es posible pero no en forma de una receta universal. Turing y godel hicieron una demostracion incorrecta pero la tesis es correcta.
1er Premio consuelo: una replica del sombrero de Hilbert. 2do Premio consuelo: una replica del Infinito gorrito (que es como la trompeta del angel Gabriel ubicada sobre una esfera de Riemann) autografiado por Mike. Saludos desde Rosario, Argentina.
Menos mal que no mencionaste que la O de la complejidad computacional es la letra ómicron, mas de algún conspiracioncita habría relacionado la pandemia con skynet
Si P=NP sería un duro golpe para la criptografía. Todo sería muy diferente: Habría que cambiar contraseñas más a menudo, las comunicaciones necesitarían más bits, o sea más lento todo. A bitcoin le iría muy mal... todo en Internet habría que redefinirlo prácticamente.
Prácticamente toda nuestra estructura de datos tal como la entendíamos sería falsa, aunque existieran contraargumentos para eso. Hasta campos como la cuántica se verían afectados
Sigue así, lo explicas tan bien. Jamás había entendido tan bien los problemas del Milenio (sé que es un entendimiento pobre, pero al menos uno se da una idea) :D
Un sumador sigue siempre los mismos pasos, quiero decir: no le toma más pasos cuando recibe un acarreo. Su tabla tiene 3 entradas A, B, C(in) y 2 salidas SUMA, C(out) Para C(in) 0 o 1. Utiliza exactamente lo mismos transistores y en el mismo tiempo. Es como si un humano sumase siempre el acarreo, aún cuando es 0.
De echo, si sigues la logica del O grande, se pueden factorizar en O(n^(1/2)/ln^(1/2)(n)) con la criba de erastotenes, que no tan mal, pero con n's de hasta 400 digitos que se usan peta
mi duda es esta(con respecto al problema de las damas y el tablero): si sabemos el funcionamiento de las reinas, que es lo que nos echa para atrás, al fin y al cabo una reina nunca va a cambiar su función, es decir , nunca va dejar de tener las cualidades que posee, por ende (conociendo por encima el ajedrez), sabemos que una reina, no interfiere con otra siempre y cuando R1(Reina 1) esté a (i=2;j=1) de R2. si nos posicionamos en el punto origen , que en un tablero n-dimensional, lo estableceríamos según nuestro criterio o las pautas preestablecidas , solo tendríamos que tener en cuenta 2 factores, el movimiento de la reina y la cantidad de movimientos que podemos hacer antes de una reina, toque su diagonal con otra. para exponerlo de otra manera: si comenzásemos en la parte superior izquierda de un tablero infinito , pero con la misma asignación de casillas(ejemplo:e4,d6,a2,etc...), podríamos ver que la función solo tiene que cambiar 1 vez y luego regresar al mismo bucle anterior: 1º algoritmo: 1:a8 2:b6 3:c4 5:d2 2º algoritmo, que se activa al no haber espacio suficiente en el eje de x(para este ejemplo) 6:g3 7:f5 8:e7 decidme que pensáis y si queréis que lo siga explicando avisadme :) (no soy un profesional ni nada , solo he puesto lo que creo con el poco conocimiento que tengo)
Justo quería preguntarle si es que podía hacer un vídeo sobre las ecuaciones Navier-Stokes, ahora apenas ví que tiene iniciada una serie sobre los problemas del milenio. 👌🏿 Muchas gracias!
No puedo esperar el estreno, hace unos días vi tu video sobre la función zeta de riemman (está difícil).Y eso q todavía estoy viendo la función gamma.😅
Me encantan estos vídeos,impresionante como se va escalando en complejidad y lo explicas de una manera que nos acerca un poco a entender semejante problema, sin duda un gran canal un gran trabajo, ✌🏻👌🏻👌🏻👌🏻
Sinceramente... soy fan de esto♡ Puse el video en el televisor y en el telefono (que tiene mi cuenta) en simultaneo para poder comentarte lo mucho que me fascina tu trabajo♡ Sueño con una sociedad de bienestar generalizado donde, gracias a eso, la cantidad de científicos e ingenieros dedicados a resolver los "problemas del milenio" estén todos reunidos en una gran casa a lo "Gran Hermano" haciendo este arte tan maravilloso que es ciencia, para el beneficio de toda la humanidad y con todos los recursos a su disposición.
Sabías que el concepto de Gran Hermano viene de una sociedad totalitaria imaginada por Orwell, no? Básicamente los querés privar a la fuerza de su libertad xD
Dame más contexto pero no lo veo haciendo eso por obligación :v @@alvarowwx Tarde o temprano se rebelan. Pero permitir que quien quiera aportar a la causa lo hagan.
hermano, podría hacer un vídeo explicando el enunciado del problema denominado "inverse galois problem"... Claro, si no es mucho pedir, ya que sé que debe estar al alcance. Es muy famoso y creo que aún está abierto. Agradecido de ante mano por su tiempo.
Pues creo que en el 1er ejemplo, un factor en el valor de n y el resultado 2n, yo diría que si todos es 1 en las dos variables, el resultado constará del doble de bit's para generar ese último 1, generando una ampliación de variable, por lo que: 1111+1111=XXX1,1110. Por lo que el resultado para hacerlo largo sería n+(2n-1) solo para valores solo sean 1
Pero creo que factorizar un número en sus factores primos puede hacerse con un algoritmo polinomico, aunque sea tardado. Entonces creo que no va por ahí lo del P vs NP
Bueno, he llegado a un veredicto: P NO ES NP, pero el álgebra nunca podría saberlo. Anoche me acordé de algo, y es que en una clase de trigonometría el profe dijo que no se conoce fórmula para calcular el coseno, así que se hace por aproximación. Así que habría simplemente que demostrar que dicha fórmula no podría existir y la aproximación es la única forma. Pues resulta ser que el coseno no cumple la primera ley de la resolución de problemas en un único ciclo de mecanismo: "Se requiere una cantidad conocida de elementos del problema o que, dada una máquina de cierta capacidad, los elementos sobrantes o faltantes se puedan completar con elementos nulos". El porqué de la ley es obvio: Si no conocés la cantidad de elementos que vas a tener que procesar, tenés que adaptar el algoritmo a cualquier número n, y éso implica un bucle y procesar uno a uno. Y no se cumple para el coseno, por un lado, porque la curva del coseno posee infinitos valles y crestas, por lo cual no es procesable sino por un bucle. Por el otro lado, si decidiéramos decir que es cíclica, por lo cual solo necesitamos la parte entre 0 y 180 grados... ¿Qué es lo que tenemos en el eje de las x?: Ángulos. Y un ángulo, por definición, es la suma de infinitos segmentos de un círculo. De hecho, ¿Es un ángulo un valor o un mero límite? Como decir "Los segmentos del círculo de acá a acá TIENDEN a sumar 6 grados" porque, le recuerdo, son infinitos segmentos así que nunca se los pudo terminar de sumar. Así que la propia curva de la función coseno proviene de una suma que, por definición, no se puede hacer. Por último, diría que la verdadera fórmula de la función coseno es la que siempre se ha utilizado para aproximarla: Un polinomio infinito. Y en ella, cada punto de la curva depende de la totalidad de los términos del polinomio. No existen elementos nulos o asimilables a nulos en el problema. Ahora bien... si no es posible crear una máquina que resuelva el coseno en un único ciclo de mecanismo, entonces tampoco es posible crear una fórmula que lo haga. Porque la relación entre ambas cosas es que una fórmula ES un ciclo de mecanismo. Aún cuando las partes internas de la fórmula solo se pudiesen resolver mediante bucles, el conjunto en sí representa un ciclo. Y a ésto el álgebra no lo podría saber, repito nuevamente, porque el álgebra no tiene en cuenta la lógica de mecanismos.
Otra condición que he descubierto es la multiplicación de soluciones, es decir, que el Sudoku propuesto, no tiene una (1) solución sino que existen algunos con cinco (5) y tengo uno de hasta veintisiete (27) soluciones. Con lo cual el concepto de "tiempo polinomios", no debería cumplirse, pues el Sudoku debe cumplir con una (1) solución única.
Mike que libro recomiendas para estudiar este tema en particular, un poco mas en profundidad, desde ya muchas gracias, soy estudiante de Ciencias Computacionales en la UBA(Universidad de Buenos Aires), y me apasiono bastante este tema, y también el millón de dólares ...
La putada es que, si es independiente y no es demostrable, la hipótesis pasa a ser infalseable y por lo tanto se tendría que descartar. Hasta que no lo descubramos no sabemos si va a ser no igual o independiente, con una la hipótesis tendría sentido y la otra no.
Es lo más adecuado cuando se habla de algoritmos, ya que es lo que se utiliza hoy en día en computación para almacenar las variables que utiliza un programa/algoritmo, y si, es obvio que también se puede utilizar cualquier otro tipo de almacenamiento como memoria de intercambio y almacenamiento (suerte ejecutando cualquier algoritmo en DVDs) pero por razones obvias la ram es superior y estándar en esta aplicación específica.
Me gusta como explicas los videos, además de los elementos gráficos que utilizas. ¿Que tal un video acerca del modelo de Maquina de Turing? Base teórica en la cual se sustentan las computadoras, se que es un tema que se aleja un poco de tu temática, pero igual no deja de ser matemáticas.
En el minuto 8:34 pones que se comprueba en una maquina de turing determinista, pero estoy casi seguro de que eso se hace en una maquina de turing NO-Determinista.
¿Sabe qué?... Voy a cambiar el enfoque, porque decir "es un error del álgebra" puede ofender a alguno por ahí. Lo explicaré de otra forma: No se puede demostrar P vs NP porque la solución cambia según las reglas que especifiques para el problema. Me explico: Imaginemos por un momento que es posible construir una máquina cuya capacidad de procesamiento fuese inferior a un bit. A medida que reducimos la capacidad hacia el infinitesimal de bit, todos los problemas para ésa máquina en particular tienden a ser NP, hasta llegar al punto teórico en que cualquier problema le lleva infinidad de tiempo el resolverlo. Si bien es sencillo comprender que éso no es posible, porque la menor unidad de procesamiento posible es el bit, no hay cómo explicarle éso al álgebra. Es una regla de validez que se debe establecer por encima de cualquier resultado que el álgebra nos pueda dar. ¿Qué hay por el otro lado? Para una máquina con capacidad de procesamiento infinita, cualquier problema es P. De hecho, ésa máquina no necesitaría calcular nada, porque para cualquier problema que le pudiésemos plantear ya tendría la solución alojada en algún lugar de su memoria. Así que obtener cualquier respuesta solo sería buscar y dar. Pero éste extremo es imposible y, de nuevo, no es factible decírselo al álgebra. De hecho ¿En qué punto la complejidad de una máquina se vuelve siquiera irrazonable? No es como el caso anterior, en que el límite es claramente un bit, sino que solo podemos decir que no es infinito, es "menos". Ahora bien, si establecemos como regla que nuestra máquina no puede conocer de antemano el resultado de un problema, sino que efectivamente debe resolverlo, entonces aplican las reglas que especifiqué antes. Es decir que para poder hacer que una máquina resuelva un problema en un único ciclo se deben dar dos condiciones... o tres: A- Que la cantidad de elementos del problema sean conocidos con antelación o, teniendo una máquina de cierta capacidad, se puedan completar los elementos faltantes o sobrantes con elementos nulos. B- Que no existan relaciones cruzadas, es decir que el resultado de un elemento por procesar no afecte el resultado de uno ya procesado. C- Que el orden de procesamiento de los elementos sea conocido. Si cualquiera de ésas tres condiciones no se cumple, el problema ya no es resoluble en un único ciclo de mecanismo, sino que se requiere un bucle de cambios de estado y obtener el resultado final progresivamente. El gran conflicto entre álgebra, aritmética y algoritmos es que el álgebra y aritmética asumen que, si ya se ha demostrado que 5 + 4 es 9, entonces es algo que "se sabe". Pero una máquina normalmente, para cada vez que se le presentan los inputs 5 y 4 para la operación suma, realiza el trabajo de validar que el resultado es, efectivamente, 9. No da nada por asumido EXCEPTO que el algoritmo sea asumir. Por ejemplo: Si para criptografía necesitamos todos los números primos entre 100 y 1000 dígitos, no es conveniente calcularlos todos de nuevo cada vez. Lo mejor es tener un archivo con todos ellos y tomarlos de ahí. Si el archivo está corrupto y/o alguno de los valores que contiene no es número primo, no es asunto de dicho algoritmo. Pero, de nuevo, no es posible explicarle todo éso al álgebra y, por lo tanto, no se puede obtener una respuesta clara sobre P Vs NP. Porque el álgebra no considera la lógica de los mecanismos y toda respuesta obtenida de ella es potencialmente errónea. No es una cuestión de si todas las variables se tuvieron en cuenta o no, sino que es imposible expresar todas las relaciones existentes entre las variables de forma algebraica. El ejemplo más claro de ello se da en economía, en la "ecuación" PQ = MV, en la cual Q no depende realmente ni de M ni de V, sino de oferta y demanda, que es otro sistema ni siquiera mencionado en la ecuación. Y no es posible expresar eso algebraicamente.
Después de saber programar en varios lenguajes de programacion de distintos paradigmas aún no entiendo el problema en su totalidad. Pero lo explicaste genial. Es el mejor video explicativo del problema
no es "programar", es un análisis que uno hace al algoritmo que crea, un análisis de costo en tiempo. programar ya forma parte de la implementación y ella se ubica en la última etapa de un proyecto. implementar es lo que poco importa.
Esta realmente bien explicado. Pero de lejos, lo que mas me ha gustado, y que a la gente le cuesta recordar o entender ha sido al principio con: "Y sacar una solucion **SI ESTA EXISTE**"
La conjetura de pointcare fue resuelta hace años por un doctor en matematicas. Cuando le ofrecieron el premio millonario, el lo rechazo al afirmar que su recompenza era haberlo resuelto.
Superchulo el vídeo! Un apunte: Una de las mayores consecuencias de resolver este problema es la criptografía y por ende toda la ciberseguridad del planeta. - Si P /= NP, darías una mayor seguridad puesto que se afirmaría que los criptosistemas son irrompibles (en tiempo polinomial). -Si P= NP, al carajo. Podrías desencriptar todo lo que quieras en un tiempo "razonable", es decir, acabas de destrozar toda la ciberseguridad del mundo, entre ella la de los bancos por ejemplo. Este problema no te da un millón de euros, te da todo el que quieras.
Destrozarías la ciberseguridad si das una demostración constructiva del problema. Si no proporcionas una forma de construir los algoritmos no hay problema
Es un tema perturbador, de manera análoga un problema = un número = una teoría Existen números que pueden ser construidos en una cantidad finita de pasos y deacuerdo a la aritmética, otros en infinitos pasos deacuerdo a la aritmética o finitos pasos no deacuerdo a la aritmética, pero cierto teorema (incompletitud) afirma que siempre existirán números/problemas/teorías que no pueden ser construid@s en una cantidad finita de pasos ni bajo las leyes de la aritmética. No todos los problemas indemostrables son igual de indemostrables así como no todos los conjuntos infinitos son igual de infinitos. Podemos romper toda la ciberseguridad que seamos capaces de crear pero no por ello quiere decir desencriptemos "todo" y que resolvamos de manera general p=np. Genial video Mike👍
gracias bacan y felices fiestas, una pregunta, cuando usted dice un input de seis bits no serian 12? puesto que entran dos números de seis cada uno? (Minuto 4 aprox) o no entendi!
Yo resolvi las 8 reinas ,primero llenando con la cantidad minima para completar el tablero que son 6, despues remover una pieza para que calcen 7 y después 8. La maquina lo podria resolver asi y su dificultad se calcularia en permutaciones. Pero te piden un tablero de mil, solo si tuviera que permutar el movimiento de 100 reinas es una valor exponencial que supera a la maquina y le tomaría años.
Como estudiante de 2° Bachillerato puede que esté diciendo alguna barbaridad por falta de conocimientos, pero... ¿no se podría averiguar si se cumple o no la igualdad partiendo de ambas premisas? 👀 En todo caso, sería ver qué "cambia" el hecho de que lo sea o no (ligeras variaciones). Por ejemplo, yo cuando quiero saber si un problema es "A" o "B" dirijo la atención al resultado que me darían ambas premisas (algo así como cuando en el laberinto que dan en los manteles de restaurantes encuentras el camino correcto partiendo del final). Tal vez sea algo estúpido y ya alguien lo haya refutado, pero bueno... 🤷
haha nisiquiera entendi el planteamiento del problema, ni soñar con resolverlo XD
3 роки тому+1
Hay muchas posibilidades de redefinir dichos problemas y todo problema computacional existente en el mundo, por ahora seguiré usando los mentados de Einstein y Hawking, para simular, dado que aunque mis idea no son soluciones finales harán que todos los problemas tipo p tengan un solución tendente a tiempo cero, este video se complementa mucho con su explicaciones: "Las Matemáticas tienen una Terrible Falla": ua-cam.com/video/RRg38oNQ9vk/v-deo.html
Excelente, me encanto la forma y toda la informacion, increible, muy bueno 🔥🔥🔥🔥🔥🔥 Excelente, me encanto la forma y toda la informacion, increible, muy bueno 🔥🔥🔥🔥🔥🔥 Excelente, me encanto la forma y toda la informacion, increible, muy bueno 🔥🔥🔥🔥🔥🔥
Tengo un programa que resuelve Sudokus, de 9x9, pero lo tengo limitado a un numero de datos determinado, porque el tiempo de consumo es exponencial de forma que no podría calcular un Sudoku de 9x9 con cero (0) datos, es decir, todas las soluciones. He de informar que tengo un ordenador modesto con un software modesto. Algo parecido me pasa con el programa de ubicación de las Damas del ajedrez que no pueden "matarse" entre ellas, de forma que el cálculo lo puedo llevar a condiciones temporales "racionales" hasta un cuadrado de tablero de 15x15, y puedo además insertar antes de calcular en el 9x9, "reinas bloqueados de posiciones"....... etc...
Apreciado @@andres_vacal Con las Damas son tablero de 15 x 15 , me salen por encima los miles de millones.... me consumio un día y medio de ordenador y seguía....., paré, no estoy para invertir mucho tiempo en estas cosas curiosas e interesante, pero improductivas económicamente, pues no gano dinero. Saludos cordiales.
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
Fe de errores: el problema de las N-damas no es NP-Completo, pero sí lo es si antes hay algunas damas sobre el tablero.
Aquí tenéis el link al paper: t.co/mk0NvGT8KZ
Mil gracias a @CarlosMarah por darse cuenta :)
Hay problemas NP completos muchísimo más sencillos de entender e investigar como el Subset Sum Problem.
Siempre me ha parecido curioso que se le dé más importancia a problemas como la hipótesis de Riemann , cuya resolución no aportaría nada nuevo (excepto las mates y el enfoque que traiga la propia demostración), que el problema PvsNP , la cual, de ser cierta, sería un impulso brutal en computación científica, en logística, en transportes..etc.
F
Es una sutileza, pero creo que no existe el diez en binario, es el uno cero
@@sparkmeister1772 El diez en binario es "1010", el dos es "10"
@@pmascaros Que en el video a dicho "diez binario" para referirse al 2 convertido a binario, pero creo que se dice "uno cero"
En realidad ya he resuelto el problema P vs. NP:
P=NP
P-NP=0
(1-N)P=0
O sea que NP=P si y solo si P=0 o N=1.
¿Dónde está mi millón de dólares?
Todo fue una broma América.
XD
Te lo tomas a broma pero eso lo más cerca que nadie estará jamás de la respuesta, sino el día que alguien encuentre el más complejo de todos los problemas P y que simultaneamente sea el menos complejo de todos los problemas NP también lo resolverá.
Jaja :d. No pues p=np es posible pero no en forma de una receta universal. Turing y godel hicieron una demostracion incorrecta pero la tesis es correcta.
1er Premio consuelo: una replica del sombrero de Hilbert.
2do Premio consuelo: una replica del Infinito gorrito (que es como la trompeta del angel Gabriel ubicada sobre una esfera de Riemann) autografiado por Mike.
Saludos desde Rosario, Argentina.
Ese ejercicio me lo dejaron de tarea cuando iba en segundo semestre de la carrera en Ingeniería, Obvio, nadie siquiera entendió la pregunta jaja
Menos mal que no mencionaste que la O de la complejidad computacional es la letra ómicron, mas de algún conspiracioncita habría relacionado la pandemia con skynet
qué me dices :o pero se escribe igual que una o???? tanto la mayúscula como la minúscula??
@@MowCueto666 Sí, exactamente igual
Oo, Οο
@@dystotera77 Válgame dios
Y yo que quería ver a un Terminator de Skynet...
O-mega = cota superior de la complejidad (peor caso). O-micron = cota inferior de la complejidad (mejor caso).
Si P=NP sería un duro golpe para la criptografía. Todo sería muy diferente: Habría que cambiar contraseñas más a menudo, las comunicaciones necesitarían más bits, o sea más lento todo. A bitcoin le iría muy mal... todo en Internet habría que redefinirlo prácticamente.
Computacionalmente todo sería predecible solo en cuestión de tiempo.
Los Primos estan en P
Que p=np, no quiere decir que encontrareis el algoritmo rapidamente, solo afirmaria que existe un algoritmo de complejidad polinomica
Prácticamente toda nuestra estructura de datos tal como la entendíamos sería falsa, aunque existieran contraargumentos para eso. Hasta campos como la cuántica se verían afectados
@@oscarlizarraga3679 Si se llega a dar que P = NP entonces los NP completos podrían ser algoritmos para la solución de todo.
Sigue así, lo explicas tan bien. Jamás había entendido tan bien los problemas del Milenio (sé que es un entendimiento pobre, pero al menos uno se da una idea) :D
normal, si de seguro nunca fuiste a la universidad
En la "universidad", creo que no enseñan esto es complejo lñ.
Aunque bueno apenas ando en 4to de secundaria Baab,.
.
Me atrevo a decir que esta nueva serie de videos, sera de las más importantes dentro de toda la comunidad de matemáticas en habla hispana.
Ya tengo ganas de que se estrene, desde ya dejo mi like. No me lo quiero perder, saludos Mike haces muy buenos vídeos.
Y otro millón para casa, cada día te volves más y más rico
Exponencialmente millonario
Un sumador sigue siempre los mismos pasos, quiero decir: no le toma más pasos cuando recibe un acarreo.
Su tabla tiene 3 entradas A, B, C(in) y 2 salidas SUMA, C(out)
Para C(in) 0 o 1. Utiliza exactamente lo mismos transistores y en el mismo tiempo.
Es como si un humano sumase siempre el acarreo, aún cuando es 0.
Me parece una excelente explicación, tratándose de un video de divulgación. Felicidades!!
Puedes hacer un video sobre lo difícil que es factorizar un número y la criptografía?
De echo, si sigues la logica del O grande, se pueden factorizar en O(n^(1/2)/ln^(1/2)(n)) con la criba de erastotenes, que no tan mal, pero con n's de hasta 400 digitos que se usan peta
@@manuelzz5970 Eso no puede ser. La factorización se sabría que esté en P. No se sabe tal cosa
Muy bien explicado, he visto otros vídeos y no lo había entendido
mi duda es esta(con respecto al problema de las damas y el tablero):
si sabemos el funcionamiento de las reinas, que es lo que nos echa para atrás, al fin y al cabo una reina nunca va a cambiar su función, es decir , nunca va dejar de tener las cualidades que posee, por ende (conociendo por encima el ajedrez), sabemos que una reina, no interfiere con otra siempre y cuando R1(Reina 1) esté a (i=2;j=1) de R2.
si nos posicionamos en el punto origen , que en un tablero n-dimensional, lo estableceríamos según nuestro criterio o las pautas preestablecidas , solo tendríamos que tener en cuenta 2 factores, el movimiento de la reina y la cantidad de movimientos que podemos hacer antes de una reina, toque su diagonal con otra. para exponerlo de otra manera:
si comenzásemos en la parte superior izquierda de un tablero infinito , pero con la misma asignación de casillas(ejemplo:e4,d6,a2,etc...), podríamos ver que la función solo tiene que cambiar 1 vez y luego regresar al mismo bucle anterior:
1º algoritmo:
1:a8
2:b6
3:c4
5:d2
2º algoritmo, que se activa al no haber espacio suficiente en el eje de x(para este ejemplo)
6:g3
7:f5
8:e7
decidme que pensáis y si queréis que lo siga explicando avisadme :)
(no soy un profesional ni nada , solo he puesto lo que creo con el poco conocimiento que tengo)
Tío me ayudas muchísimo, ayer estuve en clase de mates y me preguntaron que era g64.
Sé que no tiene nada que ver con este vídeo, pero me ayudas🤩🤗😘
Que buen Canal de matemáticas,me gusta como explica las cosas y la animación,gracias por existir. :')
Espero con ansias el video de las ecuaciones de Navier-Stokes
Excelente contenido.
Esta va a ser una de mis épocas favoritas de tu canal
Justo quería preguntarle si es que podía hacer un vídeo sobre las ecuaciones Navier-Stokes, ahora apenas ví que tiene iniciada una serie sobre los problemas del milenio. 👌🏿
Muchas gracias!
No puedo esperar el estreno, hace unos días vi tu video sobre la función zeta de riemman (está difícil).Y eso q todavía estoy viendo la función gamma.😅
La mejor explicacion que he visto del tema. Muy entendible!
🦋 Siempre estás luciéndote con tus vídeos. Le tengo mucho cariño a tu canal. Ojalá y algún día puedas hacer un tutorial de Manim.
Me encantan estos vídeos,impresionante como se va escalando en complejidad y lo explicas de una manera que nos acerca un poco a entender semejante problema, sin duda un gran canal un gran trabajo, ✌🏻👌🏻👌🏻👌🏻
Felicitaciones Mates Mike, un video muy claro, ilustrativo y concreto para describir la esencia de P vs NP.
Me encantó el vídeo y la forma que explica todo, solo me gustaría agregar que en 8:23 NP hace referencia a una máquina de Turing no determinista
Sinceramente... soy fan de esto♡ Puse el video en el televisor y en el telefono (que tiene mi cuenta) en simultaneo para poder comentarte lo mucho que me fascina tu trabajo♡
Sueño con una sociedad de bienestar generalizado donde, gracias a eso, la cantidad de científicos e ingenieros dedicados a resolver los "problemas del milenio" estén todos reunidos en una gran casa a lo "Gran Hermano" haciendo este arte tan maravilloso que es ciencia, para el beneficio de toda la humanidad y con todos los recursos a su disposición.
Sabías que el concepto de Gran Hermano viene de una sociedad totalitaria imaginada por Orwell, no? Básicamente los querés privar a la fuerza de su libertad xD
Dame más contexto pero no lo veo haciendo eso por obligación :v @@alvarowwx Tarde o temprano se rebelan. Pero permitir que quien quiera aportar a la causa lo hagan.
hermano, podría hacer un vídeo explicando el enunciado del problema denominado "inverse galois problem"... Claro, si no es mucho pedir, ya que sé que debe estar al alcance. Es muy famoso y creo que aún está abierto. Agradecido de ante mano por su tiempo.
Pues creo que en el 1er ejemplo, un factor en el valor de n y el resultado 2n, yo diría que si todos es 1 en las dos variables, el resultado constará del doble de bit's para generar ese último 1, generando una ampliación de variable, por lo que: 1111+1111=XXX1,1110. Por lo que el resultado para hacerlo largo sería n+(2n-1) solo para valores solo sean 1
El ejemplo de P NP que uso es la factorizacion en numeros primos. Es muy rapido comprobarlo y muy tardao calcularlo
Pero creo que factorizar un número en sus factores primos puede hacerse con un algoritmo polinomico, aunque sea tardado. Entonces creo que no va por ahí lo del P vs NP
Jamás he entendido la definición del problema, pero muchas felicidades.
Prietos contra No Prietos?
Xd
Lol
Prietos = N Aprietos
Prietos en aprietos
Excelente explicación Mike! Un capo 👏👏
Bueno, he llegado a un veredicto: P NO ES NP, pero el álgebra nunca podría saberlo. Anoche me acordé de algo, y es que en una clase de trigonometría el profe dijo que no se conoce fórmula para calcular el coseno, así que se hace por aproximación. Así que habría simplemente que demostrar que dicha fórmula no podría existir y la aproximación es la única forma.
Pues resulta ser que el coseno no cumple la primera ley de la resolución de problemas en un único ciclo de mecanismo: "Se requiere una cantidad conocida de elementos del problema o que, dada una máquina de cierta capacidad, los elementos sobrantes o faltantes se puedan completar con elementos nulos". El porqué de la ley es obvio: Si no conocés la cantidad de elementos que vas a tener que procesar, tenés que adaptar el algoritmo a cualquier número n, y éso implica un bucle y procesar uno a uno.
Y no se cumple para el coseno, por un lado, porque la curva del coseno posee infinitos valles y crestas, por lo cual no es procesable sino por un bucle. Por el otro lado, si decidiéramos decir que es cíclica, por lo cual solo necesitamos la parte entre 0 y 180 grados... ¿Qué es lo que tenemos en el eje de las x?: Ángulos. Y un ángulo, por definición, es la suma de infinitos segmentos de un círculo. De hecho, ¿Es un ángulo un valor o un mero límite? Como decir "Los segmentos del círculo de acá a acá TIENDEN a sumar 6 grados" porque, le recuerdo, son infinitos segmentos así que nunca se los pudo terminar de sumar. Así que la propia curva de la función coseno proviene de una suma que, por definición, no se puede hacer. Por último, diría que la verdadera fórmula de la función coseno es la que siempre se ha utilizado para aproximarla: Un polinomio infinito. Y en ella, cada punto de la curva depende de la totalidad de los términos del polinomio. No existen elementos nulos o asimilables a nulos en el problema.
Ahora bien... si no es posible crear una máquina que resuelva el coseno en un único ciclo de mecanismo, entonces tampoco es posible crear una fórmula que lo haga. Porque la relación entre ambas cosas es que una fórmula ES un ciclo de mecanismo. Aún cuando las partes internas de la fórmula solo se pudiesen resolver mediante bucles, el conjunto en sí representa un ciclo.
Y a ésto el álgebra no lo podría saber, repito nuevamente, porque el álgebra no tiene en cuenta la lógica de mecanismos.
Excelente video!
Por fin pude entender la idea detrás de p=NP
¡Buenisimo! Ahora las ecuaciones diferenciales más bonitas
Yo lo que diga la gata Noether...Seguro que vale más por lo que calla que por lo que cuenta, XD...
Vi varios videos sobre este tema, de esos, este creo que es el mas claro. Gracias
Lo has explicado mejor que cualquier otro video que he visto sobre el tema
Hola Mike, haces un gran gran trabajo felicitaciones. Quisiera saber si usas Manim para tus videos o After effects ?
Manim
@@MatesMike Si le disparas a alguien para acabar con su vida "P" es más fácil que luego comprobar si realmente ha fallecido "np"
Otra condición que he descubierto es la multiplicación de soluciones, es decir, que el Sudoku propuesto, no tiene una (1) solución sino que existen algunos con cinco (5) y tengo uno de hasta veintisiete (27) soluciones. Con lo cual el concepto de "tiempo polinomios", no debería cumplirse, pues el Sudoku debe cumplir con una (1) solución única.
Mike que libro recomiendas para estudiar este tema en particular, un poco mas en profundidad, desde ya muchas gracias, soy estudiante de Ciencias Computacionales en la UBA(Universidad de Buenos Aires), y me apasiono bastante este tema, y también el millón de dólares ...
Solo por el titulo ya te ganaste mi respeto, me encantan los sudokus
La putada es que, si es independiente y no es demostrable, la hipótesis pasa a ser infalseable y por lo tanto se tendría que descartar. Hasta que no lo descubramos no sabemos si va a ser no igual o independiente, con una la hipótesis tendría sentido y la otra no.
Yo he resuelto el problema, pero paso del millón, es más divertido ver como os rompeis la cabeza intentando resolverlo vosotros.
Por que pones una memoria ram en el min 2:50 Mike?? y Que programa utilizas??
Es lo más adecuado cuando se habla de algoritmos, ya que es lo que se utiliza hoy en día en computación para almacenar las variables que utiliza un programa/algoritmo, y si, es obvio que también se puede utilizar cualquier otro tipo de almacenamiento como memoria de intercambio y almacenamiento (suerte ejecutando cualquier algoritmo en DVDs) pero por razones obvias la ram es superior y estándar en esta aplicación específica.
Me gusta como explicas los videos, además de los elementos gráficos que utilizas. ¿Que tal un video acerca del modelo de Maquina de Turing? Base teórica en la cual se sustentan las computadoras, se que es un tema que se aleja un poco de tu temática, pero igual no deja de ser matemáticas.
👏🏼👏🏼👏🏼 gran video, por fa haz el siguiente de las ecuaciones de Navier
ESpero continues con los otros prblemas del milenio seria genial, gran video.
En el minuto 8:34 pones que se comprueba en una maquina de turing determinista, pero estoy casi seguro de que eso se hace en una maquina de turing NO-Determinista.
Gracias profesor..
Muy interesante
Me gusto el video, aunque un poco desalentador el final con la opinión de los expertos xD
Eres un fenómeno explicando muy claro todo.
5:44
Me ganó la duda.. Alguien sabe cual es ese algoritmo para la resolución de Determinantes nxn??
Gracias de antemano
¿Sabe qué?... Voy a cambiar el enfoque, porque decir "es un error del álgebra" puede ofender a alguno por ahí. Lo explicaré de otra forma: No se puede demostrar P vs NP porque la solución cambia según las reglas que especifiques para el problema. Me explico:
Imaginemos por un momento que es posible construir una máquina cuya capacidad de procesamiento fuese inferior a un bit. A medida que reducimos la capacidad hacia el infinitesimal de bit, todos los problemas para ésa máquina en particular tienden a ser NP, hasta llegar al punto teórico en que cualquier problema le lleva infinidad de tiempo el resolverlo. Si bien es sencillo comprender que éso no es posible, porque la menor unidad de procesamiento posible es el bit, no hay cómo explicarle éso al álgebra. Es una regla de validez que se debe establecer por encima de cualquier resultado que el álgebra nos pueda dar.
¿Qué hay por el otro lado? Para una máquina con capacidad de procesamiento infinita, cualquier problema es P. De hecho, ésa máquina no necesitaría calcular nada, porque para cualquier problema que le pudiésemos plantear ya tendría la solución alojada en algún lugar de su memoria. Así que obtener cualquier respuesta solo sería buscar y dar.
Pero éste extremo es imposible y, de nuevo, no es factible decírselo al álgebra. De hecho ¿En qué punto la complejidad de una máquina se vuelve siquiera irrazonable? No es como el caso anterior, en que el límite es claramente un bit, sino que solo podemos decir que no es infinito, es "menos".
Ahora bien, si establecemos como regla que nuestra máquina no puede conocer de antemano el resultado de un problema, sino que efectivamente debe resolverlo, entonces aplican las reglas que especifiqué antes. Es decir que para poder hacer que una máquina resuelva un problema en un único ciclo se deben dar dos condiciones... o tres:
A- Que la cantidad de elementos del problema sean conocidos con antelación o, teniendo una máquina de cierta capacidad, se puedan completar los elementos faltantes o sobrantes con elementos nulos.
B- Que no existan relaciones cruzadas, es decir que el resultado de un elemento por procesar no afecte el resultado de uno ya procesado.
C- Que el orden de procesamiento de los elementos sea conocido.
Si cualquiera de ésas tres condiciones no se cumple, el problema ya no es resoluble en un único ciclo de mecanismo, sino que se requiere un bucle de cambios de estado y obtener el resultado final progresivamente.
El gran conflicto entre álgebra, aritmética y algoritmos es que el álgebra y aritmética asumen que, si ya se ha demostrado que 5 + 4 es 9, entonces es algo que "se sabe". Pero una máquina normalmente, para cada vez que se le presentan los inputs 5 y 4 para la operación suma, realiza el trabajo de validar que el resultado es, efectivamente, 9. No da nada por asumido EXCEPTO que el algoritmo sea asumir. Por ejemplo: Si para criptografía necesitamos todos los números primos entre 100 y 1000 dígitos, no es conveniente calcularlos todos de nuevo cada vez. Lo mejor es tener un archivo con todos ellos y tomarlos de ahí. Si el archivo está corrupto y/o alguno de los valores que contiene no es número primo, no es asunto de dicho algoritmo.
Pero, de nuevo, no es posible explicarle todo éso al álgebra y, por lo tanto, no se puede obtener una respuesta clara sobre P Vs NP. Porque el álgebra no considera la lógica de los mecanismos y toda respuesta obtenida de ella es potencialmente errónea. No es una cuestión de si todas las variables se tuvieron en cuenta o no, sino que es imposible expresar todas las relaciones existentes entre las variables de forma algebraica. El ejemplo más claro de ello se da en economía, en la "ecuación" PQ = MV, en la cual Q no depende realmente ni de M ni de V, sino de oferta y demanda, que es otro sistema ni siquiera mencionado en la ecuación. Y no es posible expresar eso algebraicamente.
Bro piensa que somos su chat
Después de saber programar en varios lenguajes de programacion de distintos paradigmas aún no entiendo el problema en su totalidad. Pero lo explicaste genial. Es el mejor video explicativo del problema
no es "programar", es un análisis que uno hace al algoritmo que crea, un análisis de costo en tiempo.
programar ya forma parte de la implementación y ella se ubica en la última etapa de un proyecto.
implementar es lo que poco importa.
3:53 este signo de la bandera argentina te lo agradecemos Mike Math 😃❤️😍🇦🇷🇦🇷🇦🇷🇦🇷🇦🇷🇦🇷👍⛄
Esta realmente bien explicado.
Pero de lejos, lo que mas me ha gustado, y que a la gente le cuesta recordar o entender ha sido al principio con: "Y sacar una solucion **SI ESTA EXISTE**"
Su videos son muy buenos, és na minha opinion uno de los mejores canais del youtube.
9:13 Y si en el caso de que yo tenga la respuesta a eso de las damas?
Y de hecho SI ES NP-completa?
Molan mucho tus vídeos!
¡Genial resumen! La teoría de la computación es muy interesante y tiene mucha utilidad; igual es buena fuente para futuros vídeos ;)
Es buen momento para decir que a las justas sé geometría de colegio.
La conjetura de pointcare fue resuelta hace años por un doctor en matematicas. Cuando le ofrecieron el premio millonario, el lo rechazo al afirmar que su recompenza era haberlo resuelto.
Me encanta tu canal, habla sobre las ecuaciones de Navier-Stokes.
Y donde está Jordi NP ?
no entiendo nada pero igual lo veo
Superchulo el vídeo! Un apunte:
Una de las mayores consecuencias de resolver este problema es la criptografía y por ende toda la ciberseguridad del planeta.
- Si P /= NP, darías una mayor seguridad puesto que se afirmaría que los criptosistemas son irrompibles (en tiempo polinomial).
-Si P= NP, al carajo. Podrías desencriptar todo lo que quieras en un tiempo "razonable", es decir, acabas de destrozar toda la ciberseguridad del mundo, entre ella la de los bancos por ejemplo. Este problema no te da un millón de euros, te da todo el que quieras.
Destrozarías la ciberseguridad si das una demostración constructiva del problema. Si no proporcionas una forma de construir los algoritmos no hay problema
Es un tema perturbador, de manera análoga un problema = un número = una teoría
Existen números que pueden ser construidos en una cantidad finita de pasos y deacuerdo a la aritmética,
otros en infinitos pasos deacuerdo a la aritmética o finitos pasos no deacuerdo a la aritmética,
pero cierto teorema (incompletitud) afirma que siempre existirán
números/problemas/teorías que no pueden ser construid@s en una cantidad finita de pasos ni bajo las leyes de la aritmética.
No todos los problemas indemostrables son igual de indemostrables así como no todos los conjuntos infinitos son igual de infinitos. Podemos romper toda la ciberseguridad que seamos capaces de crear pero no por ello quiere decir desencriptemos "todo" y que resolvamos de manera general p=np.
Genial video Mike👍
Video de Mike nuevo y encima estreno de Halo Infinite que buen estreno
no entiendo como puede entretenerme o gustarme esto si según yo hace años que no quería ver más problemas complejos de matemática
Te entendí más a ti que a mi profesor de informática teórica, muchas gracias.
LA RESPUESTA DEL ULTIMO ES "NPI"
(NI PUTA IDEA)
gracias, mil gracias, realmente con vos me cayo la ficha en este tema
Me encantan este tipo de videos aun sin tener ni idea de matemáticas, pero, mi pregunta es, ¿Se sabe que pueden tener una hipotética solución?
No que ya había salido el video??? Estaba en un playlist con el video de la hipótesis de Riemann😐
Genial, este video va a ser muy épico. Apenas leí el título dije: Ummm, esto me interesa.
Me parecen fascinante estos problemas matemáticos aunque no los entienda totalmente. Una duda ¿que carrera estudiaste Mike?
Estudié Matemáticas e Ingeniería Aeroespacial :)
Si quieres puedes ver el #pyr 2, ahí cuenta un poco de eso
Mike, 5:35, ¿qué algoritmos son los más eficientes para la suma y el producto? ¿Cuánto más eficientes?
Uff cuando me dieron esto en complejidad computacional en la u me rompio la cabeza, pero tu lo explicas muy bien
Un millón de dólares es poco, este problema merece un premio de 10 000 000 millones
El siguiente que sea el de Navier Stokes!
Que estresante que UA-cam no recomiende canales de matemáticas
MIKE Buenos videos broo 🔥
Aureo + 2 es primo?
y porqué no desarrollamos Inteligencias artificiales que desarrollen Algoritmos para esto?
gracias bacan y felices fiestas, una pregunta, cuando usted dice un input de seis bits no serian 12? puesto que entran dos números de seis cada uno? (Minuto 4 aprox) o no entendi!
gracias, ¡me ha encantado y he aprendido! ¡Crack!
Yo resolvi las 8 reinas ,primero llenando con la cantidad minima para completar el tablero que son 6, despues remover una pieza para que calcen 7 y después 8. La maquina lo podria resolver asi y su dificultad se calcularia en permutaciones. Pero te piden un tablero de mil, solo si tuviera que permutar el movimiento de 100 reinas es una valor exponencial que supera a la maquina y le tomaría años.
Gracias gracias gracias hermanos ❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️
Bro, anteayer estaba buscando cosas de este problema.
Deja de leerme la mente.
Por favor y gracias
Ya estaba suscrito desde hace tiempo, pero justo me sale este video el 24 de mayo jaja
Hasta ahora es la mejor explicación que he visto.
Como estudiante de 2° Bachillerato puede que esté diciendo alguna barbaridad por falta de conocimientos, pero... ¿no se podría averiguar si se cumple o no la igualdad partiendo de ambas premisas? 👀
En todo caso, sería ver qué "cambia" el hecho de que lo sea o no (ligeras variaciones).
Por ejemplo, yo cuando quiero saber si un problema es "A" o "B" dirijo la atención al resultado que me darían ambas premisas (algo así como cuando en el laberinto que dan en los manteles de restaurantes encuentras el camino correcto partiendo del final).
Tal vez sea algo estúpido y ya alguien lo haya refutado, pero bueno... 🤷
Lo que tu sugieres es demostración por contradicción, quiero creer, pero dudo mucho que en éste caso pueda aplicarse dada la naturaleza del problema.
Es una joya este video, se entiende mas sobre la materia de "Analisis y diseño de algoritmos"
haha nisiquiera entendi el planteamiento del problema, ni soñar con resolverlo XD
Hay muchas posibilidades de redefinir dichos problemas y todo problema computacional existente en el mundo, por ahora seguiré usando los mentados de Einstein y Hawking, para simular, dado que aunque mis idea no son soluciones finales harán que todos los problemas tipo p tengan un solución tendente a tiempo cero, este video se complementa mucho con su explicaciones: "Las Matemáticas tienen una Terrible Falla": ua-cam.com/video/RRg38oNQ9vk/v-deo.html
El otro día me presentaron este problema
La parte del gato diciendo hasta luego xd con el tablero grande y ls 8 dams no s epq me dio tanta gracia
12:00
yo, que juego a ambos regularmente:
f por maincra xd
Excelente, me encanto la forma y toda la informacion, increible, muy bueno 🔥🔥🔥🔥🔥🔥
Excelente, me encanto la forma y toda la informacion, increible, muy bueno 🔥🔥🔥🔥🔥🔥
Excelente, me encanto la forma y toda la informacion, increible, muy bueno 🔥🔥🔥🔥🔥🔥
Y pensar que esto inicio con Alan Turing :0
Tengo un programa que resuelve Sudokus, de 9x9, pero lo tengo limitado a un numero de datos determinado, porque el tiempo de consumo es exponencial de forma que no podría calcular un Sudoku de 9x9 con cero (0) datos, es decir, todas las soluciones. He de informar que tengo un ordenador modesto con un software modesto.
Algo parecido me pasa con el programa de ubicación de las Damas del ajedrez que no pueden "matarse" entre ellas, de forma que el cálculo lo puedo llevar a condiciones temporales "racionales" hasta un cuadrado de tablero de 15x15, y puedo además insertar antes de calcular en el 9x9, "reinas bloqueados de posiciones"....... etc...
Que complejidad te da el de las Damas con un 15x15?
Apreciado @@andres_vacal Con las Damas son tablero de 15 x 15 , me salen por encima los miles de millones.... me consumio un día y medio de ordenador y seguía....., paré, no estoy para invertir mucho tiempo en estas cosas curiosas e interesante, pero improductivas económicamente, pues no gano dinero. Saludos cordiales.