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
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.
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
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!
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.
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.😅
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.
¿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.
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.
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 ...
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, ✌🏻👌🏻👌🏻👌🏻
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.
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
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.
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.
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.
En relación con la compresión de datos, creo que Claude Shannon se equivocó al confundir los átomos y la materia con los datos, que informáticamente solo son número. Entiendo que el concepto de "compresión" de la información es erroneo, porque los números no pueden "comprimirse" pero sí codificarse. Creo que mediante el algoritmo adecuado, se pueden codificar números muy grandes conviertiéndolos en cifras mucho más pequeñas, por medio de un proceso recursivo (por ejemplo, codificar 1 Gigabyte en solo 1 Megabyte). Me gustaría saber que implicancias tendría que se demostrase esta posibilidad de codificación de la información mucho más allá del límite de compresión de Shannon en relación con el tema que trata este interesante video... 🤔 Un saludo.
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.
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.
NO, VIEJO, mejor di que este canal es solo para los que les gustan las matemáticas de manera innata. Hay algo que se llama inteligencia desabstractiva, y los matemáticos, como tú, carecen casi por completo de ella. Lo siento.
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... 🤷
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!
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.
No se si esta solucion sea valida de alguna forma, pero el problema de las reinas se puede resolver de forma polinomial siempre y cuando estemos hablando de un tablero de n*n, simplemente te vas a la casilla de arriba a la izquierda del todo, pones una reina, bajas 2 casillas y avanzas una a la derecha, pones otra reina y repites esta proceso hasta llegar a la fila 2, luego subes n-2 casillas y avanzas una a la derecha, pones otra reina y, como antes, avanzas uno a la derecha y 2 hacia abajo hasta llegar a la esquina del tablero
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👍
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**"
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.
Si N=NP también N debería ser casi intratable por lo tanto N podría ser en realidad un NP con cierta factor que vuelva lo intratable el algo tratable por lo cual N=NP con X,Y o Z factor interviniendo lo cual haga del NP un problema intratable por su complejidad a un problema con menos cursos a tomar el cual vuelva este mismo intratable por lo cual en realidad un problema N podría haber sido en realidad un problema NP que al restringir o agregar un factor X,Y o Z este haya pasado de intratable a uno con menos formas de tratar. Tal que un lotgaritmo de los ya utilizados actualmente podrían ser mejorados al combinarlo con otro que haga la parte de discriminar cierta información lo que haría la realización de NP mucho más sencilla PD: Escribí esto a las 3 de la mañana no me juzguen
¿Pero no puedes, por ejemplo, en el sudoku, rellenar todos los huecos con números al azar y después comprobar el resultado? Digo eso seria polinomial no?
Lo que estarias haciendo, es aplicar un metodo no determinista, por ende no seria polinomial, sino exponencial. En este caso, deberia hacerse un calculo probabilistico dependiendo de en que iteracion se resuelve el problema.
Hola, dos cosas. Los algoritmos que utilizan decisiones al azar como lo que comentas se llaman algoritmos probabilísticos, aunque fueran polinomiales, este tipo de algoritmos ya no se consideran dentro de P. Se consideraría entonces PP. Y no sé si estoy entendiendo bien lo que propones, pero si ya hay algunos números y rellenaras con números al azar los que faltan, seguramente no hallarías una solución a la primera, ni segunda...seria casi por fuerza bruta y necesitarías aproximadamente probar la mitad de las posibles combinaciones y esas son muchísimas.
El número se puede aproximar mediante permutaciones con repetición. Por ejemplo para el de 9 x 9 serian algo así como: 81!/(9!)⁹ Depende completamente del algoritmo, pero lo más probable es que la complejidad sea factorial , mucho peor que exponencial.
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.
Cordial saludo; me gustaría tener la oportunidad de presentar la solución al enigma informático matemático P vs NP... Estoy buscando apoyo porque varias entidades me están pidiendo seder mis derechos de autor. Que debo hacer. Mil gracias
De hecho solo tendría sentido mostrar el trabajo si se demuestra que no son iguales porque si encuentras una forma de convertir problemas resueltos en tiempo exponencial a tiempo polinomial "destruyes" la criptografía. Un millón de dólares no es nada comparado con lo que podrías hacer conociendo dicho algoritmo
Demostrar lo opuesto también es increíblemente útil, con el mismo ejemplo se demostraría que la criptografía es realmente útil y en de alguna manera irrompible.
Una vez leí una discusión en una lista de una universidad que argumentaba que debe decirse "P vs NP" y no "P no igual NP". No entendí nada de esa discusión. Hay alguna sutileza entre "versus" e "igual" que se me escapó ?
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? Esta afirmación de Mike es correcta?, es decir, entiendo que hizo el despeje de la variable N y P y aquello le dio un resultado, pero mi pregunta es ¿saber esto sirve de algo o a partir de aquí que es lo que seguiría?... no es broma jsjs, tengo esa duda
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.
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.
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.
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,.
.
Y otro millón para casa, cada día te volves más y más rico
Exponencialmente millonario
Ya tengo ganas de que se estrene, desde ya dejo mi like. No me lo quiero perder, saludos Mike haces muy buenos vídeos.
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
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🤩🤗😘
Me parece una excelente explicación, tratándose de un video de divulgación. Felicidades!!
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!
Esta va a ser una de mis épocas favoritas de tu canal
Espero con ansias el video de las ecuaciones de Navier-Stokes
Excelente contenido.
Muy bien explicado, he visto otros vídeos y no lo había entendido
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.
Que buen Canal de matemáticas,me gusta como explica las cosas y la animación,gracias por existir. :')
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.😅
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.
¿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
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
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.
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 ...
🦋 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 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
Jamás he entendido la definición del problema, pero muchas felicidades.
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, ✌🏻👌🏻👌🏻👌🏻
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.
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
Felicitaciones Mates Mike, un video muy claro, ilustrativo y concreto para describir la esencia de P vs NP.
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.
Prietos contra No Prietos?
Xd
Lol
Prietos = N Aprietos
Prietos en aprietos
La mejor explicacion que he visto del tema. Muy entendible!
5:44
Me ganó la duda.. Alguien sabe cual es ese algoritmo para la resolución de Determinantes nxn??
Gracias de antemano
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.
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"
Excelente explicación Mike! Un capo 👏👏
Y donde está Jordi NP ?
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.
Yo he resuelto el problema, pero paso del millón, es más divertido ver como os rompeis la cabeza intentando resolverlo vosotros.
No que ya había salido el video??? Estaba en un playlist con el video de la hipótesis de Riemann😐
no entiendo nada pero igual lo veo
En relación con la compresión de datos, creo que Claude Shannon se equivocó al confundir los átomos y la materia con los datos, que informáticamente solo son número.
Entiendo que el concepto de "compresión" de la información es erroneo, porque los números no pueden "comprimirse" pero sí codificarse.
Creo que mediante el algoritmo adecuado, se pueden codificar números muy grandes conviertiéndolos en cifras mucho más pequeñas, por medio de un proceso recursivo (por ejemplo, codificar 1 Gigabyte en solo 1 Megabyte).
Me gustaría saber que implicancias tendría que se demostrase esta posibilidad de codificación de la información mucho más allá del límite de compresión de Shannon en relación con el tema que trata este interesante video... 🤔
Un saludo.
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.
¡Buenisimo! Ahora las ecuaciones diferenciales más bonitas
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.
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?
Lo has explicado mejor que cualquier otro video que he visto sobre el tema
NO, VIEJO, mejor di que este canal es solo para los que les gustan las matemáticas de manera innata. Hay algo que se llama inteligencia desabstractiva, y los matemáticos, como tú, carecen casi por completo de ella. Lo siento.
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.
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
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!
Vi varios videos sobre este tema, de esos, este creo que es el mas claro. Gracias
Solo por el titulo ya te ganaste mi respeto, me encantan los sudokus
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.
Me gusto el video, aunque un poco desalentador el final con la opinión de los expertos xD
ESpero continues con los otros prblemas del milenio seria genial, gran video.
No se si esta solucion sea valida de alguna forma, pero el problema de las reinas se puede resolver de forma polinomial siempre y cuando estemos hablando de un tablero de n*n, simplemente te vas a la casilla de arriba a la izquierda del todo, pones una reina, bajas 2 casillas y avanzas una a la derecha, pones otra reina y repites esta proceso hasta llegar a la fila 2, luego subes n-2 casillas y avanzas una a la derecha, pones otra reina y, como antes, avanzas uno a la derecha y 2 hacia abajo hasta llegar a la esquina del tablero
Excelente video!
Por fin pude entender la idea detrás de p=NP
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
👏🏼👏🏼👏🏼 gran video, por fa haz el siguiente de las ecuaciones de Navier
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
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**"
Es buen momento para decir que a las justas sé geometría de colegio.
LA RESPUESTA DEL ULTIMO ES "NPI"
(NI PUTA IDEA)
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?
Un millón de dólares es poco, este problema merece un premio de 10 000 000 millones
Te entendí más a ti que a mi profesor de informática teórica, muchas gracias.
No hay tal cosa como diez en binario (dos base diez), al ser otra base y no estar definida no se debe tratar como otras bases solo como referencias.
El siguiente que sea el de Navier Stokes!
Mike, 5:35, ¿qué algoritmos son los más eficientes para la suma y el producto? ¿Cuánto más eficientes?
Yo lo que diga la gata Noether...Seguro que vale más por lo que calla que por lo que cuenta, XD...
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.
Uff cuando me dieron esto en complejidad computacional en la u me rompio la cabeza, pero tu lo explicas muy bien
Y pensar que esto inicio con Alan Turing :0
Si
N=NP también N debería ser casi intratable por lo tanto
N podría ser en realidad un NP con cierta factor que vuelva lo intratable el algo tratable por lo cual N=NP con X,Y o Z factor interviniendo lo cual haga del NP un problema intratable por su complejidad a un problema con menos cursos a tomar el cual vuelva este mismo intratable por lo cual en realidad un problema N podría haber sido en realidad un problema NP que al restringir o agregar un factor X,Y o Z este haya pasado de intratable a uno con menos formas de tratar.
Tal que un lotgaritmo de los ya utilizados actualmente podrían ser mejorados al combinarlo con otro que haga la parte de discriminar cierta información lo que haría la realización de NP mucho más sencilla
PD: Escribí esto a las 3 de la mañana no me juzguen
Genial, este video va a ser muy épico. Apenas leí el título dije: Ummm, esto me interesa.
¿Pero no puedes, por ejemplo, en el sudoku, rellenar todos los huecos con números al azar y después comprobar el resultado? Digo eso seria polinomial no?
Lo que estarias haciendo, es aplicar un metodo no determinista, por ende no seria polinomial, sino exponencial. En este caso, deberia hacerse un calculo probabilistico dependiendo de en que iteracion se resuelve el problema.
Hola, dos cosas. Los algoritmos que utilizan decisiones al azar como lo que comentas se llaman algoritmos probabilísticos, aunque fueran polinomiales, este tipo de algoritmos ya no se consideran dentro de P. Se consideraría entonces PP.
Y no sé si estoy entendiendo bien lo que propones, pero si ya hay algunos números y rellenaras con números al azar los que faltan, seguramente no hallarías una solución a la primera, ni segunda...seria casi por fuerza bruta y necesitarías aproximadamente probar la mitad de las posibles combinaciones y esas son muchísimas.
El número se puede aproximar mediante permutaciones con repetición. Por ejemplo para el de 9 x 9 serian algo así como: 81!/(9!)⁹
Depende completamente del algoritmo, pero lo más probable es que la complejidad sea factorial , mucho peor que exponencial.
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.
Hola! consulta... cual es el algoritmo mas eficiente para el determinante de matrices?
No c
@@felizianosole896 :(
La parte del gato diciendo hasta luego xd con el tablero grande y ls 8 dams no s epq me dio tanta gracia
Gracias profesor..
Muy interesante
Cordial saludo; me gustaría tener la oportunidad de presentar la solución al enigma informático matemático P vs NP... Estoy buscando apoyo porque varias entidades me están pidiendo seder mis derechos de autor. Que debo hacer. Mil gracias
Gracias gracias gracias hermanos ❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️
Tenía una duda y era si con "problema" te refieres a cualquier "problema". Osea "P vs NP" es un problema del tipo P o del tipo NP?
De hecho solo tendría sentido mostrar el trabajo si se demuestra que no son iguales porque si encuentras una forma de convertir problemas resueltos en tiempo exponencial a tiempo polinomial "destruyes" la criptografía. Un millón de dólares no es nada comparado con lo que podrías hacer conociendo dicho algoritmo
Demostrar lo opuesto también es increíblemente útil, con el mismo ejemplo se demostraría que la criptografía es realmente útil y en de alguna manera irrompible.
Yo ya he resuelto el problema de las N Reinas con reinas ya colocadas en el tablero, que debo hacer ahora?
Una vez leí una discusión en una lista de una universidad que argumentaba que debe decirse "P vs NP" y no "P no igual NP". No entendí nada de esa discusión. Hay alguna sutileza entre "versus" e "igual" que se me escapó ?
El argumento de esa discusion que sugiere debe ser del tipo "independiente".
Su videos son muy buenos, és na minha opinion uno de los mejores canais del youtube.
no me quedo muy claro que es el MP Completo, me lo podrian explicar de nuevo ese solamente
Bro, anteayer estaba buscando cosas de este problema.
Deja de leerme la mente.
Por favor y gracias
y porqué no desarrollamos Inteligencias artificiales que desarrollen Algoritmos para esto?
Molan mucho tus vídeos!
El otro día me presentaron este problema
Ojalá subas pronto el de la Conjetura de Birch y Swinnerton-Dyer
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?
Esta afirmación de Mike es correcta?, es decir, entiendo que hizo el despeje de la variable N y P y aquello le dio un resultado, pero mi pregunta es ¿saber esto sirve de algo o a partir de aquí que es lo que seguiría?... no es broma jsjs, tengo esa duda
Con todo el respeto que te mereces te preguntaré si es una broma. Si no lo es, te respondo con mucho gusto.
amigo es joda o decís enserio perdon
Bruh