El Mayor Problema de la Computación SIN RESOLVER

■ Patreon: / matesmike
■ Miembros del canal: / @matesmike
■ Instagram: @mates.mike
■ Twitter: @mike_mates
Hoy es el turno de la Teoría de la computación: el problema P versus NP. Nos vamos a mover por el mundo de los programas y los algoritmos, así que veamos primero qué es a lo que nos referimos con uno.
►► ALGUNOS VÍDEOS:
► SAGA DEL INFINITO: • La Paradoja del Hotel ...
► SAGA DEL FACTORIAL: • ¿Qué es el Factorial e...
► LA HIPÓTESIS DE RIEMANN: • El Patrón de los Númer...
► El Orden de los Factores SÍ altera el Producto: • El Orden de los Factor...
► Cómo Dividir Entre 0 Sin Colapsar el Universo:
• Cómo Dividir entre 0 s...
►Ecuaciones y fractales: • Cómo CREAR FRACTALES c...

[@MatesMike]

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 :)

[@pmascaros]

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.

[@browncatlol9653]

F

[@sparkmeister1772]

Es una sutileza, pero creo que no existe el diez en binario, es el uno cero

[@pmascaros]

@@sparkmeister1772 El diez en binario es "1010", el dos es "10"

[@sparkmeister1772]

@@pmascaros Que en el video a dicho "diez binario" para referirse al 2 convertido a binario, pero creo que se dice "uno cero"

[@MatesMike]

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?

[@Maxwell-ox8ul]

Todo fue una broma América.

[@juampabaquero5407]

XD

[@pedrosuarez544]

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á.

[@lacasadeacero]

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.

[@jagatiello6900]

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.

[@emmanuelayala4832]

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

[@JotaGonAgu]

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.

[@renzoneru]

Computacionalmente todo sería predecible solo en cuestión de tiempo.

[@jagatiello6900]

Los Primos estan en P

[@oscarlizarraga3679]

Que p=np, no quiere decir que encontrareis el algoritmo rapidamente, solo afirmaria que existe un algoritmo de complejidad polinomica

[@PositronQ]

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

[@felix-gena6595]

@@oscarlizarraga3679 Si se llega a dar que P = NP entonces los NP completos podrían ser algoritmos para la solución de todo.

[@hishan.farfan]

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

[@MowCueto666]

qué me dices :o pero se escribe igual que una o???? tanto la mayúscula como la minúscula??

[@dystotera77]

@@MowCueto666 Sí, exactamente igual Oo, Οο

[@MowCueto666]

@@dystotera77 Válgame dios

[@fabianezequielcortez4544]

Y yo que quería ver a un Terminator de Skynet...

[@ale_gallardo]

O-mega = cota superior de la complejidad (peor caso). O-micron = cota inferior de la complejidad (mejor caso).

[@raulescorpio]

Problema del milenio: **sale en un video de un youtuber de mates** El vato que a duras penas aprobó matemática en la secundaria: a casa platita 🤑🤑🤑🤑🤑

[@felizianosole896]

Bis

[@Draozyrk]

yukari

[@raulescorpio]

@@Draozyrk pero con pito

[@angelacosta7936]

XD

[@alancito98]

Como si enseñaran bien matemáticas en el colegio (al menos en LATAM) Yo me aprendi toda la mate desde aritmética hasta calculo en un año, it's not a big deal

[@galvanromerovictorhugo4iv590]

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

[@Franco23119]

normal, si de seguro nunca fuiste a la universidad

[@jfaunoframed8190]

En la "universidad", creo que no enseñan esto es complejo lñ.

[@jfaunoframed8190]

Aunque bueno apenas ando en 4to de secundaria Baab,. .

[@Alexis-kg1sm]

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.

[@Athenas_Owl]

Ya tengo ganas de que se estrene, desde ya dejo mi like. No me lo quiero perder, saludos Mike haces muy buenos vídeos.

[@GabriTell]

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... 🤷

[@alejandrohernandez4576]

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.

[@mariamerelas9793]

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🤩🤗😘

[@Kevin-14]

Y otro millón para casa, cada día te volves más y más rico

[@locotus11sax24]

Exponencialmente millonario

[@guill3978]

Puedes hacer un video sobre lo difícil que es factorizar un número y la criptografía?

[@manuelzz5970]

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

[@orlandomoreno6168]

@@manuelzz5970 Eso no puede ser. La factorización se sabría que esté en P. No se sabe tal cosa

[@JJ-xc1ho]

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!

[@ricklosmultiplayer7830]

Esta va a ser una de mis épocas favoritas de tu canal

[@margaritareyessierra8795]

Me parece una excelente explicación, tratándose de un video de divulgación. Felicidades!!

[@NIVOLAY_]

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)

[@NemoNihil07]

Espero con ansias el video de las ecuaciones de Navier-Stokes Excelente contenido.

[@MrPery121]

Muy bien explicado, he visto otros vídeos y no lo había entendido

[@rolandojosse5123]

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.😅

[@Maxwell-ox8ul]

Que buen Canal de matemáticas,me gusta como explica las cosas y la animación,gracias por existir. :')

[@Imaginolua]

Jamás he entendido la definición del problema, pero muchas felicidades.

[@frankush10]

no entiendo nada pero igual lo veo

[@jesusfigueroa6678]

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.

[@faller222]

El ejemplo de P NP que uso es la factorizacion en numeros primos. Es muy rapido comprobarlo y muy tardao calcularlo

[@11100039]

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

[@elgiank2914]

Prietos contra No Prietos?

[@ASTRA_U1]

🦋 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.

[@cesaresquivelcruz5855]

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

[@mateodeboca1299]

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 ...

[@dannya.j.gomez-ramirez5313]

Felicitaciones Mates Mike, un video muy claro, ilustrativo y concreto para describir la esencia de P vs NP.

[@Gustavo-xt9gp]

Me gusto el video, aunque un poco desalentador el final con la opinión de los expertos xD

[@drjackal007]

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, ✌🏻👌🏻👌🏻👌🏻

[@olmedo6214]

No que ya había salido el video??? Estaba en un playlist con el video de la hipótesis de Riemann😐

[@Heveryt0]

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

[@JAAP2101]

La mejor explicacion que he visto del tema. Muy entendible!

[@joseferrerjimenez4756]

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.

[@leotuculito]

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.

[@alvarowwx]

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

[@leotuculito]

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.

[@iquniversity6595]

¡Buenisimo! Ahora las ecuaciones diferenciales más bonitas

[@ladosisdemath8961]

Hola Mike, haces un gran gran trabajo felicitaciones. Quisiera saber si usas Manim para tus videos o After effects ?

[@MatesMike]

Manim

[@lasantazapatillahace12anos43]

​@@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"

[@suicraft8395]

Solo por el titulo ya te ganaste mi respeto, me encantan los sudokus

[@El_Girasol_Fachero]

Excelente explicación Mike! Un capo 👏👏

[@leonardobarrera2816]

Por que pones una memoria ram en el min 2:50 Mike?? y Que programa utilizas??

[@felix-gena6595]

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.

[@ernestomiguelbagur408]

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.

[@nightmike7655]

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.

[@ikerkhazix4519]

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

[@Leonardoacosta287]

Excelente video! Por fin pude entender la idea detrás de p=NP

[@octaviopadron7519]

El siguiente que sea el de Navier Stokes!

[@gmates8537]

Video de Mike nuevo y encima estreno de Halo Infinite que buen estreno

[@JoseCastro-gk2kw]

Gracias profesor.. Muy interesante

[@randombrandol238]

Me parecen fascinante estos problemas matemáticos aunque no los entienda totalmente. Una duda ¿que carrera estudiaste Mike?

[@MatesMike]

Estudié Matemáticas e Ingeniería Aeroespacial :)

[@juampabaquero5407]

Si quieres puedes ver el #pyr 2, ahí cuenta un poco de eso

[@ulisesfigueroa5096]

Hola Mike, saludos

[@itlos3704]

Lo has explicado mejor que cualquier otro video que he visto sobre el tema

[@shuyin69]

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?

[@samglass3727]

Muy buen video

[@MILK-iq2tl]

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.

[@ivandossantos9168]

Esperaba esto

[@eduaispuru9501]

Vi varios videos sobre este tema, de esos, este creo que es el mas claro. Gracias

[@Athenas_Owl]

Genial, este video va a ser muy épico. Apenas leí el título dije: Ummm, esto me interesa.

[@marcoss1212]

La parte del gato diciendo hasta luego xd con el tablero grande y ls 8 dams no s epq me dio tanta gracia

[@Maxwell-ox8ul]

OOOOOHHHH,YA SALIO.

[@2acristian]

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.

[@renzoneru]

Y pensar que esto inicio con Alan Turing :0

[@xd100josesanchez2]

ESpero continues con los otros prblemas del milenio seria genial, gran video.

[@ermamaso4385]

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**"

[@vixo0105]

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

[@David_Rg]

12:00 yo, que juego a ambos regularmente: f por maincra xd

[@cabor8296]

Bro, anteayer estaba buscando cosas de este problema. Deja de leerme la mente. Por favor y gracias

[@danielmendez7443]

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.

[@neosebas8272]

Eres un fenómeno explicando muy claro todo.

[@jdpantoja442]

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.

[@Vaccaei]

Yo he resuelto el problema, pero paso del millón, es más divertido ver como os rompeis la cabeza intentando resolverlo vosotros.

[@ernestomiguelbagur408]

¿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.

[@estebangadacz2919]

El problema que lo refuta completamente es el del viajante, el camino mínimo con grafos, demostrar que por lo menos ese problema solo se puede resolver con complejidad exponencial. Hay otro de probabilidad condicionada en la ruleta o en blackjack21 pero es más difícil de exponer para convencer que es un algoritmo. Saludos.

[@PotatoBTD6]

Para refutar N=NP cualquier problema NP sirve, ni siquiera tiene que ser NP completo. Por ejemplo, si pruebas que la factorización no está en P, ¡pum! ¡ganaste un millón de dólares!

[@gustavorc25]

@@PotatoBTD6 Si hay varios casos de donde agarrar ¿por qué todavía no hay ganador? XDD

[@estebangadacz2919]

@@PotatoBTD6 la factorización se hace O(logn), tiene orden logarítmico, yo desentrañé a los números primos y otros temas. Saludos.

[@andresfelipemirandasilva6887]

Y que hay del Tetris ?se demostró que es np completo y que incluso es de los más difíciles de resolver de la clase np

[@Xion746]

Te entendí más a ti que a mi profesor de informática teórica, muchas gracias.

[@Wariowa345]

hay una forma de resolver el problema de las damas generalizado sin exponencial eso lo aprendi jugando en paginas de algoritmos es bastante ingenioso, pero cuando te obligan a empezar con una dama ahi se complica y se usa otro algoritmo que puede no funcionar porque usa la aleatoridad, algo muy curioso es que yo cuando me empezó a gustar los algoritmos yo me hice la misma pregunta, de si hay alguna razon por la que es imposible completar cualquier problema en un tiempo relativo a el tamaño de las entradas, lo intente resolver pero es como intentar atrapar un gas con una canasta, me entere hace poco que el problema ya se conocía y parece ser aun mas dificil de que me imagine, muy buen video

[@lalinski2322]

Ya estaba suscrito desde hace tiempo, pero justo me sale este video el 24 de mayo jaja

[@marcosm4691]

Buen video

[@Shergiok]

¡Me encanta este canal! :D

[@dar8580]

Me encanta tu canal, habla sobre las ecuaciones de Navier-Stokes.

[@luzstellarestrepo6277]

Sería interesante que nos hables de las ecuaciones de navier stokes

[@Jose1959-ky7tl]

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.

[@cristianarango4369]

👏🏼👏🏼👏🏼 gran video, por fa haz el siguiente de las ecuaciones de Navier

[@gustavolinaresvillegas2140]

Es una joya este video, se entiende mas sobre la materia de "Analisis y diseño de algoritmos"

[@jorge_pb8482]

Uff cuando me dieron esto en complejidad computacional en la u me rompio la cabeza, pero tu lo explicas muy bien

[@sirjuliusdeviscensus114]

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!

[@elpelicanojiji]

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

[@redhe171]

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.

[@franciscojesusmancini9472]

Y donde está Jordi NP ?

[@DavidMM255]

Molan mucho tus vídeos!

[@agustinbs]

gracias, mil gracias, realmente con vos me cayo la ficha en este tema

[@Maxwell-ox8ul]

Que buen video. :D

[@hugoiglesias4892]

¿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?

[@iExoceS]

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.

[@Bumbucho]

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.

[@Bumbucho]

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.

[@naznaram3219]

Ojalá subas pronto el de la Conjetura de Birch y Swinnerton-Dyer

[@angel-ig]

¡Genial resumen! La teoría de la computación es muy interesante y tiene mucha utilidad; igual es buena fuente para futuros vídeos ;)

[@cesar-nm9mp]

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

[@felix-gena6595]

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.

[@sheshitarshc]

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.

[@dacchanneldac8742]

Su videos son muy buenos, és na minha opinion uno de los mejores canais del youtube.

[@trashjazz]

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?

[@camilojaramillovalencia7657]

Hasta ahora es la mejor explicación que he visto.

[@fabianpazos7618]

Gracias gracias gracias hermanos ❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️