Alberto nos cuenta el problema de ¿P=NP?

Summary

El guion del video expresa la indignación del narrador ante la mala comprensión de la capacidad de los ordenadores y la complejidad de ciertos problemas computacionales. Expone que los ordenadores no realizan operaciones instantáneamente y utiliza el ejemplo de calcular subconjuntos de un conjunto para ilustrar la rápida expansión de problemas a medida que aumenta su tamaño. Además, se menciona la historia del ajedrez y el grano de arroz para enfatizar la naturaleza exponencial de ciertos problemas y cómo esto afecta la viabilidad de ciertos algoritmos, terminando con una reflexión sobre los problemas NP y NP-completos, y la pregunta fundamental de si P es igual a NP.

Takeaways

• 😡 El video comienza con la indignación del narrador sobre cómo a menudo se malinterpreta un problema específico relacionado con la capacidad de los ordenadores.
• 💻 Se desmiente la creencia popular de que los ordenadores pueden realizar operaciones instantáneamente, y se explica que las operaciones computacionales toman tiempo, incluso si es una fracción de segundo.
• 🎥 Se utiliza el ejemplo de la compilación de videos para ilustrar que las tareas computacionales pueden ser demandantes y tomar un tiempo significativo para completarse.
• 🔢 Se introduce el concepto de subconjuntos y la fórmula matemática detrás de ellos, 2^n, para demostrar cómo rápidamente crece la complejidad de ciertos problemas a medida que aumenta el tamaño del conjunto.
• 🐘 Se cuenta la historia del ajedrez y el sabio para ilustrar el crecimiento exponencial y las consecuencias de no comprender la magnitud de tales crecimientos.
• 📚 Se discuten los problemas NP y NP-completos, destacando la diferencia entre ser capaz de resolver un problema en tiempo polinomial (clasificado como P) y ser capaz de verificar una solución en tiempo polinomial (clasificado como NP).
• 🤔 Se cuestiona la relación entre los conjuntos P y NP, planteando la pregunta de si P es igual a NP, una de las preguntas abiertas más importantes en la teoría de la computación.
• 💰 Se menciona el premio del Instituto Clay de un millón de dólares para quien pueda resolver la pregunta de si P es igual a NP, destacando la importancia y el impacto de tal descubrimiento.
• 🔒 Se discute cómo la resolución de si P es igual a NP tiene implicaciones significativas para la seguridad en Internet, la criptografía y la capacidad de descifrar información.
• 🎬 Se hace referencia a una película que trata sobre los matemáticos que resuelven el problema P vs. NP, sugiriendo las consecuencias dramáticas y potenciales cambios en el mundo.
• 📘 Se utiliza el ejemplo de las canciones en CDs para explicar el concepto de problemas NP-completos y la dificultad de encontrar soluciones en tiempo polinomial.

Q & A

¿Por qué dice el narrador que el video es producto de su indignación?

El narrador menciona que el video es producto de su indignación porque observa un problema que no se explica bien y a menudo se cuenta mal, lo que le parece indignante.

¿Cuál es el ejemplo que el narrador da para ilustrar que los ordenadores no realizan operaciones instantáneamente?

El narrador utiliza el ejemplo de compilar un video, que tarda un tiempo en realizarse, para demostrar que los ordenadores no hacen operaciones de forma instantánea.

¿Cuántos subconjuntos hay en un conjunto con tres elementos según la fórmula matemática mencionada?

Según la fórmula 2 elevado a n, donde n es el número de elementos del conjunto, con tres elementos habría 2 elevado a 3, es decir, ocho subconjuntos.

¿Qué es el cuento de la invención del ajedrez que el narrador relata?

Es el cuento de un visir en la India que recibe un ajedrez como regalo y, al querer recompensar al sabio que lo creó, este pide un grano de arroz en cada casilla del tablero, el doble de la casilla anterior, lo que resulta en una cantidad asombrosa de arroz.

¿Cuál es la cantidad de arroz que el sabio pide al final del cuento, en términos matemáticos?

Al final del cuento, la cantidad de arroz que el sabio pide es representada por 2 elevado a 64, una cantidad enorme que supera la producción de arroz de varios siglos.

¿Qué relación hay entre el cuento del ajedrez y la discusión sobre la capacidad de los ordenadores?

El cuento del ajedrez ilustra cómo una función exponencial, como la del ejemplo de los granos de arroz, puede crecer de manera rápida y ser inmanejable, similar a como lo sería calcular todos los subconjuntos de un conjunto grande en un ordenador.

¿Qué es lo que el narrador define como 'un problema np completo'?

Un problema np completo es uno de los problemas más difíciles dentro de los problemas np, y si se resuelve uno de ellos en tiempo polinomial, se podría resolver cualquier otro problema np también en tiempo polinomial.

¿Cuál es la diferencia fundamental entre los problemas de la clase P y los problemas de la clase NP?

La diferencia fundamental es que los problemas de la clase P son aquellos que se pueden resolver en tiempo polinomial, mientras que los problemas de la clase NP son aquellos para los que se puede verificar una solución en tiempo polinomial, pero no necesariamente resolverlos.

¿Por qué es importante la pregunta de si P es igual a NP?

Es importante porque si se demuestra que P es igual a NP, tendría implicaciones profundas en áreas como la seguridad informática, ya que muchos problemas que actualmente son difíciles de resolver se podrían resolver rápidamente.

¿Qué es el premio que ofrece el Instituto Clay por resolver el problema de P vs NP?

El Instituto Clay ofrece un premio de un millón de dólares a quien pueda resolver la cuestión de si P es igual a NP, que es uno de los problemas del milenio.

¿Qué ejemplo da el narrador para ilustrar la diferencia entre resolver y verificar una solución en el contexto de los problemas np?

El narrador da el ejemplo de saber cuántos CDs son necesarios para almacenar un número de canciones, lo cual es un problema np completo, y verificar si un conjunto de CDs contiene todas las canciones, que es más sencillo.

Outlines

00:00

😕 Indignación por la mala explicación de la capacidad de los ordenadores

El primer párrafo expresa la indignación del autor ante la mala comprensión que la gente tiene sobre las capacidades de los ordenadores. Se discute la creencia errónea de que los ordenadores pueden realizar un número ilimitado de operaciones de manera instantánea. El autor utiliza el ejemplo de la compilación de videos para demostrar que las operaciones de un ordenador no son instantáneas y que el tiempo de procesamiento puede ser significativo, especialmente cuando se realizan tareas complejas como el cálculo de todos los subconjuntos de un conjunto, lo cual es un problema exponencial que puede ser abordado matemáticamente como 2^n, donde n es el número de elementos en el conjunto.

05:01

🧮 La historia del ajedrez y la demostración de la función exponencial

El segundo párrafo profundiza en el concepto de la función exponencial a través de la historia del ajedrez en la India. Se narra el cuento del sabio que pide granos de arroz en una progresión exponencial, lo cual resulta en una cantidad asombrosa de granos, ilustrando así la naturaleza rápida y descontrolada del crecimiento exponencial. El autor compara esta historia con las operaciones de un ordenador y cómo, a medida que aumenta el tamaño del conjunto (n), el número de subconjuntos (2^n) se vuelve impracticable para ser calculado, incluso por una computadora.

10:02

🔒 La importancia de los algoritmos eficientes en la informática

El tercer párrafo se centra en la importancia de los algoritmos eficientes en la informática. Se hace hincapié en que no todos los problemas pueden ser resueltos rápidamente por un ordenador y que la eficiencia de un algoritmo depende de su capacidad para manejar el tamaño de la entrada de datos (n). Se introducen los conceptos de algoritmos polinomiales y exponenciales, y se argumenta que solo los algoritmos polinomiales son prácticamente útiles debido a su capacidad para manejar cantidades razonables de datos sin un tiempo de procesamiento prohibitivo.

15:05

🤔 El misterio de P vs. NP y sus implicaciones

El cuarto párrafo explora el famoso problema de P vs. NP, que es fundamental en la teoría de la computación. Se explica que P representa los problemas que se pueden resolver en tiempo polinomial, mientras que NP son aquellos problemas para los que se puede verificar una solución en tiempo polinomial. El autor discute la distinción entre poder resolver un problema y poder verificar una solución, y cómo la relación entre P y NP es una de las mayores incógnitas en la informática. También se menciona el premio del Instituto Clay Mathematics por la resolución de este problema.

20:06

🐺 El cuento de los tres chanchitos y el lobo: un cambio de tema

El último párrafo proporciona un cambio radical de tema, pasando de la discusión técnica sobre informática a un cuento infantil sobre los tres chanchitos y el lobo. Se narra la historia en verso, donde los chanchitos desobedientes son llevados por el lobo después de salir a pasear sin permiso. El cuento se presenta de manera tradicional y no tiene conexión directa con el contenido técnico de los párrafos anteriores.

Keywords

💡Indignación

La indignación es un sentimiento de enfado o descontento que se siente al ver algo injusto o inaceptable. En el video, el locutor menciona que su indignación es la razón por la que decide hablar sobre un problema que no se explica bien, lo que indica que el tema del video es algo que le preocupa y que cree que merece más atención y explicación correcta.

💡Ordenador

Un ordenador es un dispositivo electrónico que puede realizar operaciones matemáticas y procesamiento de datos de forma automática. En el video, se menciona que a menudo se cree que los ordenadores pueden realizar operaciones instantáneamente, pero esto no es cierto, lo que introduce el tema de las limitaciones de los ordenadores y cómo estas limitaciones afectan la forma en que se percibe su capacidad de procesamiento.

💡Subconjuntos

Un subconjunto es una parte de un conjunto que contiene algunos o todos los elementos del conjunto original. En el video, se utiliza el ejemplo de calcular todos los subconjuntos de un conjunto para ilustrar la idea de que algunos problemas computacionales pueden ser muy complejos y tomar un tiempo significativo para resolver, incluso para un ordenador.

💡Expoentes

En matemáticas, los exponentes se utilizan para multiplicar un número por sí mismo un número determinado de veces. En el video, se menciona que la cantidad de subconjuntos de un conjunto es 2 elevado a la n, donde n es el número de elementos del conjunto. Esto ilustra cómo los problemas computacionales pueden crecer exponencialmente en complejidad con el tamaño del conjunto.

💡Ajedrez

El ajedrez es un juego de tablero que se menciona en el video para ilustrar la idea de crecimiento exponencial. La historia del visir y el sabio muestra cómo el número de granos de arroz en el tablero de ajedrez crece exponencialmente, lo que es un buen ejemplo de cómo algunas situaciones pueden escalar de manera inmanejable rápidamente.

💡Tiempo polinomial

En informática, un algoritmo de tiempo polinomial es aquel que su tiempo de ejecución crece a un ritmo que es un polinomio del tamaño de la entrada. En el video, se argumenta que los algoritmos de tiempo polinomial son los que son prácticamente útiles, ya que aquellos que requieren un tiempo exponencial pueden ser inútiles debido a su lentitud.

💡P y NP

P y NP son clasificaciones de problemas en la teoría de la complejidad computacional. P se refiere a los problemas que se pueden resolver en tiempo polinomial, mientras que NP se refiere a los problemas para los cuales se puede verificar una solución en tiempo polinomial. En el video, se discute la relación entre estos dos conjuntos y la pregunta abierta de si P es igual a NP.

💡NP Completo

Los problemas NP completos son aquellos que son los más difíciles dentro de la clase NP. En el video, se explica que si se puede resolver un problema NP completo en tiempo polinomial, entonces todos los problemas NP también se pueden resolver en tiempo polinomial, lo que implicaría que P es igual a NP.

💡Seguridad en Internet

La seguridad en Internet se menciona en el video en el contexto de las claves de cifrado y la protección de la información. Se argumenta que si se pudiera demostrar que P es igual a NP, podría tener implicaciones significativas para la seguridad en Internet, ya que muchos sistemas de cifrado dependen de la dificultad de resolver ciertos problemas NP para mantener la seguridad de la información.

💡Cuento

El cuento es una forma de narrativa que se utiliza en el video para ilustrar conceptos complejos de una manera más accesible. En este caso, se utiliza el cuento del ajedrez para explicar la idea de crecimiento exponencial y cómo puede afectar a la resolución de problemas computacionales.

Highlights

El video aborda la indignación del creador por la mala explicación de problemas relacionados con la capacidad de los ordenadores.

Se desmiente la idea de que los ordenadores pueden realizar operaciones instantáneamente.

Se explica que la compilación de vídeos y otras tareas exigentes puede tomar tiempo significativo.

Se introduce la idea de que el número de operaciones que un ordenador puede realizar no es ilimitado y puede requerir tiempo.

Se menciona la fórmula matemática para calcular el número de subconjuntos de un conjunto, que es 2^n.

Se ilustra la idea de crecimiento exponencial con el ejemplo de calcular subconjuntos de un conjunto grande.

Se cuenta la historia del ajedrez y el sabio para demostrar la idea de crecimiento exponencial y sus consecuencias.

Se describe la imposibilidad de satisfacer la demanda de arroz en la historia del ajedrez debido al crecimiento exponencial.

Se discute la importancia de diferenciar entre problemas que se pueden resolver rápidamente (en tiempo polinomial) y aquellos que no lo son (en tiempo exponencial).

Se introduce la distinción entre los conjuntos P y NP en la teoría de la computación.

Se explica que si un problema es P, también es NP, pero no necesariamente viceversa.

Se menciona el premio millonario del Instituto Clay por resolver el problema de si P es igual a NP.

Se discute la importancia de los problemas NP completos y su relación con la dificultad de resolver problemas NP.

Se argumenta que resolver un problema NP completo en tiempo polinomial permitiría resolver todos los problemas NP en tiempo polinomial.

Se menciona la relevancia de la pregunta P vs NP para la seguridad en internet y la criptografía.

Se ilustra la diferencia entre comprobar una solución y encontrar una solución con el ejemplo de los CDs y las canciones.

Se destaca la complejidad de problemas NP completos y su impacto en la resolución de otros problemas NP.

Se concluye con la importancia de la distinción entre P y NP y su impacto en la teoría de la computación y la práctica.

Transcripts

[Música]

los tres

[Música]

chanchitos Este vídeo es en algún

sentido producto de de mi indignación de

mi indignación porque veo que hay un

problema un problema que que merece la

pena conocerse y demás y que no siempre

se explica bien Mejor dicho muchas veces

se explica muy mal y cuando digo muy mal

lo que quiero decir es que se cuenta mal

el enunciado del problema porque se

cuentan mal las condiciones se cuentan

mal Qué significa eh eh es más se dice

completamente al revés completamente al

revés me voy a

centrar la idea es la siguiente vamos a

empezar por un

ordenador creemos siempre que un

ordenador puede hacer tantas operaciones

como nos dé la gana y que es casi

instantáneo Pero eso no es así y eso no

es así porque hay veces que le exigimos

a los ordenadores hacer muchas

operaciones Bueno a lo mejor alguno Por

ejemplo si ha compilado vídeos y cosas

de ese estilo verá que ahora estáis

viendo un vídeo pues este vídeo se tarda

un tiempo en compilar porque lo hacemos

de alguna forma especial o le queremos

poner imágenes como vamos a poner aquí

un poco más para adelante etcétera

entonces eso tarda un tiempo en compilar

Por qué es eso bueno porque aunque

creemos que haces las operaciones

instantáneamente pues pero no es cierto

tarda una cierta fracción de segundo en

realizar cada una de sus operaciones

y hay veces que le exigimos mucho voy a

poner un ejemplo supongamos que queremos

calcular algo que para ello necesitamos

calcular todos los subconjuntos de un

conjunto bueno existe una fórmula

matemática que nos dice que todos los

subconjuntos cuántos subconjuntos tiene

un conjunto y cuántos son pues 2 elevado

a n donde n es el número de elementos

del conjunto o sea por ejemplo si

tenemos tres elementos pues existen 2

elevado a 3 ocho subconjuntos que parece

muy manejable o si alguien está diciendo

Pues eso seguro que lo hace rápido

ordenador efectivamente 2 elevado a 3 lo

hace muy rápido un ordenador incluso 2

elevado a 5 sería 32 Pues también me lo

hace muy rápido y 2 elevado a 10 también

poco más de 1000 también me lo hace muy

rápido incluso algo más pero como

vayamos subiendo el el ns el 2 elevado n

pues la función va creciendo mucho es lo

que se llama una función

exponencial para ilustrarlo un poco pues

hay famoso cuento de de la invención de

la ajedrez Entonces se supone que había

un visir en la India que estaba aburrido

y un sabio de su reino pues le le creó

el ajedrez y se lo regaló y eso le

proporcionó infinitas horas no infinitas

pero muchas horas de regocijo y de

placer a ese visir y entonces pues lo

quiso recompensar le llam al sabio dice

ven tú para acá qué quieres Y entonces

el sabio dijo bueno pues yo lo lo que

quiero es un grano de arroz en la

primera casilla del ajedrez dos en la

siguiente cuatro en la tercera y así en

cada casilla el doble de granos que es

la casilla anterior y esos granos de

arroz me lo

das el visir dijo Mira no te has

enterado bien me has proporcionado miles

de horas de placer y yo lo que quiero es

soy una persona rica enormemente rica la

persona más rica del mundo y muy muy

generosa quisiera eh recompensarte Como

es debido pídeme oros pídeme tierra

Pídeme lo que quieras entonces el sabio

dijo No no no con eso me conformo con

eso me conformo ahora bien si no me

pagas ese arroz de aquí al final de

semana o de aquí a una semana pues me

tienes que dar tu reino me das tu reino

dice el otro Bueno ya que insistes en

ser tan mísero pues Vale entonces el

visir pues llamó a su ministro de

hacienda o Quien fuera y Oye calcúlame

cuánto arroz hay que darle a ese

desgraciado el ministro de hacienda que

sabía un poco más de números pues eh se

buscó un par de de de contables que le

ayudaran a saber cuántos rozas hacía

falta y y ya al final pues al final de

la semana cuando se estaba terminando el

plazo ya fueron con una cantidad al al

visir el visir al ver aquella cantidad

que le tenía que darse quedó claro

estupefacto se quedó vamos una cosa

Terrible y entonces pues Yo supongo que

haría lo único Aunque eso no lo cuenta

del todo bien la historia pero yo te

quiero suponer que el visir haría lo

único razonable que hay que hacer en

esas ocasiones que es cortarle la cabeza

al sabio porque sería muy sabio pero se

había pasado de listo por qué Porque le

estaba pidiendo tanto arroz tanto arroz

que no había arroz en el reino eh para

satisfacer esa demanda

eh o sea con con el grado de producción

actual de la producción anual de arroz

haría falta la las cosechas de 400 años

400 años como la producción de ahora que

es mucho mayor que en el pasado para

poder satisfacer esa demanda eso es 2

elevado a a 64 para los más puristas 2

elevado 64 men1 o sea le quitamos un

granito a 2 elevado a 64 Y ese es un

número ingente obsérvese que antes hemos

dicho que 2 elevado a 3 era pequeño que

2 elevado a 5 era pequeño también 2

elevado a 10 que era razonable pues ya 2

elevado a 64 que no hay mucha diferencia

es un número absolutamente

ingente me gusta dar una imagen visual

de Qué significa 2 elevado 64 cojamos

una moneda de 1 y pongamos encima otra

moneda de 1 eur y encima dos monedas de

euro y así hasta formar una pila de

monedas de euro de do elevado a 64

monedas de 1 eur qué altura tendría esa

pila Bueno pues alguien puede pensar que

estamos en Sevilla porquees superaría la

giralda y efectivamente superaría a la

giralda superaría a lo mejor a la tor y

efectivamente lo supera o al edificio al

bus califa este que es el edificio más

alto del mundo incluso superaría la

altura de leveres incluso es mucho mayor

que la distancia de aquí a la luna y no

solo eso sino de aquí al sol que está 8

minutos luz porque de hecho esa

pila tiene mayor distancia tiene mayor

altura que la distancia de aquí a las

tres estrellas siguientes o sea porque

tiene 4,5 más de 4,5 Eh Años luz de

altura una pila de monedas de 4,5 años

luz de altura o sea una cosa

absolutamente ingente y claro eso un

ordenador si le decimos a un ordenador

calcúlame los subconjuntos de un

conjunto con 64 elementos Bueno nada

absolutamente imposible porque no hay

ordenador que haga eso en la tierra

posiblemente lo hará Porque necesitamos

más tiempo del que ha pasado hasta ahora

en en la edad del universo O sea que es

absolutamente imposible est esto qué

quiere decir supongamos que tenemos un

problema y vamos a centrarnos un poco

supongamos que tenemos un problema y

tenemos un algoritmo un método que se lo

podemos meter al ordenador y que

resuelve dicho problema no basta con

tener un método que resuelva el problema

lo que hay que tener es un método que lo

resuelva en un tiempo

razonable claro el tiempo razonable

dependerá del tamaño de de la entrada o

sea si le metemos un conjunto con n

elementos Pues dependerá de ese n si el

n es pequeñito Pues a lo mejor el tiempo

es más fácil pero queremos que el

algoritmo no crezca mucho el número de

operaciones que no crezca mucho el

número de operaciones en función del

número de de datos de la entrada de

Cuántos datos tiene nuestra entrada

Entonces si el número de operaciones que

tenemos que realizar es del orden de 2

elevado a n si es exponencial ese

algoritmo desde un punto de vista

práctico

es es absolutamente inútil no sirve para

nada entonces por lo tanto nos tenemos

que centrar en algoritmos que no sean

del tipo exponencial que haga menos de

una cantidad exponencial de operaciones

normalmente lo que buscamos son

algoritmos que hagan una cantidad

polinomial de aplicaciones de perdón de

de operaciones polinomio es aquello que

estudiábamos

en en la secundaria de 4n cu + 7n cu +

2n + 3 eso es un polinomio que ese sea

el número de operaciones en función de n

el tamaño de entrada vale Bueno pues ya

sabemos lo que son algoritmos eh

polinomiales que hacen número polinomial

de operaciones y algoritmos

exponenciales para nosotros los

exponenciales no valen para nada no

solucionan ningún problema mientras que

los polinomiales son Guay de acuerdo

Entonces supongamos que tenemos un

problema y hemos encontrado un algoritmo

que lo resuelva en cualquier caso

siempre en tiempo polinomial pues

decimos que ese ese problema el problema

ese que teníamos es un un problema que

lo podemos resolver bien se puede

resolver bien y decimos que ese problema

pertenece al conjunto p p mayúscula Vale

entonces si un problema lo podemos

resolver en tiempo polinomial decimos

que ese problema es

p bien Ahora supongamos que tenemos otro

problema y no conocemos ningún algoritmo

que lo pueda resolver en tiempo

polinomial no conocemos entonces ese

problema no sabemos si es un si es un

problema de p o no es un problema de p

porque no conocemos ningún algoritmo

bien pero ahora supongamos que vamos a

hacer otra cosa no vamos a intentar

resolver el problema tenemos un problema

otro problema del que hemos considerado

anteriormente el cual en principio no

sabemos resolverlo no tenemos ningún

algoritmo que lo resuelve en tiempo

polinomial pero sí pero sí que tenemos

un algoritmo que comprueba si nos da una

solución en tiempo polinal

voy a dar un ejemplo por ejemplo

supongamos que tengamos que hacer un

sudoku tenemos un sudoku delante nuestra

resolver el sudoku es relativamente

complicado o puede ser muy complicado

pero comprobar si una solución es una

solución válida del sudoc si nos dan el

sudoc resuelto nos dicen Oye

compruébamelo eso es simple y rutinario

bueno pues A eso me refiero o sea

tenemos nos da un problema y podemos

hacer dos cosas con el problema uno

intentar encontrar una solución y la

otra es intentar comprobar si algo es

solución de ese problema Algo que nos

dan que nos dan ya es comprobar si algo

es solución del problema Bueno pues si

tenemos un problema y podemos resolverlo

en tiempo polinomial decimos que es p Y

si podemos comprobar que algo es la

solución del problema en tiempo también

polinomial decimos que el problema es np

evidentemente si un problema es p lo

podemos resolver en tiempo polinomial

también podemos comprobar probar si algo

es solución en tiempo polinomial mi

mismo algoritmo de antes me vale por

tanto todo problema que esté en p está

en

np tenemos esta situación de aquí

tenemos p Y tenemos np Perdón que es lo

que se llama un superconjunto

bien pues la gran cuestión una de las

cuestiones que plantea el Instituto Clay

es que si p es igual a np o dicho de

otra forma están estrictamente p

incluido dentro dnp o los dos conjuntos

es en realidad son iguales hasta ahora

nadie nadie ha encontrado un problema

que sea np y que se pueda demostrar que

no es p eso no lo ha encontrado nadie

hasta ahora y si alguien es capaz de

encontrar un problema que sea np y no

sea p vale un millón de dólares que nos

paga el Instituto cl no solo un millón

de dólares vale mucho más porque en

realidad te harías mundialmente famosa

ha completado uno de los problemas del

milenio el Instituto Clay proponía siete

problemas de los cuales hasta ahora solo

se ha

eh resuelto uno lo que era la conjetura

de puen caré por gory perelman que por

cierto no lo cobró no fue a cobrarlo y

el millón ese pero sí se ha gastado el

millón de dólares el millón de dólares

se ha dedicado Pues a crear una una beca

y demás para jóvenes investigadores que

estudien problemas así similares

entonces Ese es el único que se ha

resuelto de los otros el más simple que

hay para enunciar es el p = a np y la

gente pues se confunden y dicen que p

es que se puede resolver fácil y que np

es que no se puede resolver fácil lo

cual no tiene ningún sentido como sus

conjuntos y demás como o sea unos se

pueden resolver fáciles y otros no se

pueden resolver fáciles y la pregunta es

si los dos conjuntos son iguales pues

evidentemente no si uno no se puede

resolver fácil no puede ser que que no

se pueda resolver fácil es una de

dicotomía El problema correcto es p es

que se puede comprobar fácilmente Perdón

p es que se puede encontrar fácilmente

una solución y np es que se puede

comprobar fácilmente que algo es una

solución y esa es la diferencia bueno

para complicar un poco más la la cosa

aparece una colección de

problemas principio de los 70 una

colección de problemas que es

absolutamente mágica que es lo que se

llam los problemas np completos en algún

sentido los problemas np completos son

los más difíciles entre todos los nps y

qué significan los más difíciles lo que

significa es lo siguiente que si tomamos

un problema

eh cualquiera np lo podemos reducir a a

uno de los problemas np completos de tal

forma que si resolvi el np completo en

tiempo polinomial de forma fácil

podríamos resolver el otro que hemos

cogido anteriormente también en tiempo

polinomial entonces cualquier problema

np se puede reducir a un problema np

completo lo cual es una magia esa clase

es absolutamente mágica Por qué Porque

lo que significa es que si encontramos

un solo problema np completo que sea p

encontramos un algoritmo sencillo para

resolver un problema np completo solo

uno todos los demás problemas np

completos y no solo todos los demás

problemas np completos también todos los

problemas np se resuelven en tiempo p

eso significa que si un solo problema np

completo pertenece a p la clase np es

igual a p exactamente iguales

evidentemente si uno solo de los

problemas np completo

demostrárselo investigadores que de

verdad ocurren y la otra alternativa es

probar que np es igual a p en el primer

caso podéis ir al instituto cre cobrar

vuestro millón y os

haréis ricos y famosos porque os van a

llover las invitaciones en el otro caso

si demostráis que np es igual p hay que

andarse con más cuidado hay incluso

papers

eh diciendo qué hay que hacer si uno

fuera capaz de demostrar eso por qué

Porque es que resulta que toda la

seguridad en internet y cuando digo toda

la seguridad

me refiero a claves de bancos a a todas

las comunicaciones a todo lo que

tengamos almacenado en la nube y no en

la nube Porque podríamos acceder a

cualquier ordenador etcétera etcétera

etcétera todas nuestras claves todo se

podría descifrar de forma sencilla

entonces incluso hay una película Este

es el cartel de la película donde

plantea que cuatro matemáticos consiguen

resolver el problema p = np y que llegan

a la conclusión de que p es igual a np Y

entonces bueno no lo voy a desvelar del

todo pero no lo pasan del todo bien esos

matemáticos no lo pasan del todo bien

porque pensas una cosa que es más barato

eh cambiar todo el mundo tal como lo

tenemos establecido en la actualidad o a

cuatro

matemáticos bueno Y esto es todo

cochinitos buo T parecida yo no me he

enterado de una pu bien estamos

peres Es que yo Soy torpe porque es que

no hombre pero ad si tú te enteres que

no son Yo es que no entiendo eso de

comprobar y

solucionar porque es que aquí hay dos

problemas no están los p que tú has

dicho que son los que se pueden resolver

en un tiempo razonable sí y los np son

los que yo puedo comprobar una solución

una solución en tiempo razonable déjame

que te intente poner un ejemplo Ya sé

que hoy en día no se llevan mucho los eh

en los CDs pero imagínate recuerdas en

que del siglo XX eres en el siglo XX se

utilizaban unos CDs y tal Y eso Entonces

suponte que tienes tú una colección

de de 1000 canciones de 100 canciones

las que sea en CD no Ah las tienes en tu

ordenador y las quieres pasar a

CD vale vas a necesitar mucho tiempo

pero también vas a necesitar saber

cuántos CDs necesitas

vale tú tienes 15 canciones canciones y

necesitas saber cuántos cedes Bueno

claro uno dice Bueno pues muy sencillo

divido la capacidad de cada uno de los

CD por la duración de cada una de las

canciones y y y ya me me cabe Pero no

vale por qué porque cada una cada

canción tiene una longitud entonces

puede ser que en una que en un CD sobre

para meter un minuto y medio pero no lo

quieres meter porque sería romper una

canción etcétera no Entonces a lo mejor

si quitas esta canción de este CD y lo

metes en este otro CD pues mejora Bueno

ese problema el problema de saber

cuántos CDs hacen falta para almacenar

tal número de canciones es un problema

que es np de hecho es más es np completo

de eso que habíamos dicho de los más

difíciles por qué porque tú no sabes a

priori no existe ningún algoritmo que me

diga Cuántos CDs necesitas Wow vale por

eso hemos acabado con ellos es más es

más si te digo Oye te caben todos tus

canciones en estos 25 discos tú no

tienes ningún algoritmo que lo pueda

calcular fácilmente si caben esos 25

discos pero ahora bien en un tiempo

razonable en un tiempo razonable pero

ahora bien si tú me das los 25 discos y

me dices Mira mira a ver si están las 15

canciones aquí pues yo me puedo poner a

contar todas las canciones y si están

todas digo sí si están todas esto es una

solución al problema Ah que pillines

para que veas entonces lo que tú estás

queriendo decirme es que si yo ahora me

he hecho en mi casa y encuentro un

problema que puedo comprobar la solución

es decir que puedo contar por ejemplo lo

de las canciones pero no se puede

demuestro que no se puede resolver en

tiempos polinomiales razonable Entonces

en ese caso has probado que p es

distinto de P y te llevas medio millón

de porque me medio millón medio millón

medio millón instituto Clay estamos

vamos a por vosotros estáis testigos eh

medio millón cada si lo resuel Y

entonces si el resuelvo

efectivamente pero si tengo la mala

suerte de comprobar que este problema

que puedo comprobar la solución en un

tiempo razonable además puedo encontrar

la solución en un tiempo razonable tengo

un problema gordo de ese problema en

concreto ese problema es np completo y

si de ese das un algoritmo que me

permite decir siempre en un tiempo

razonable Cuántos discos necesito para

meter tal número de canciones me van a

matar Seguro sí están muerto sí Pero

bueno también Es verdad que eh tus

amigos o la gente que te conocía Y eso

diremos Ah pues este murió porque

resolvi lo de np igual a p muerto por la

ciencia es la ilusión de mi vida sí sí

sí sí sí Ahora ya está ahora está mejor

Gracias pero macho vaya ejemplo del

siglo XX has puesto Eh bueno te puedo

poner otros pero pero de este siglo

sí los matemáticos son así viven anclado

en el pasado

Bueno pero digo yo una cosa Esto lo

habéis resuelto ya y no se lo habéis

dicho a nadie verdad es mentira eh

mentira

voy los tres

[Música]

chanchitos muy bien

ahora toca a los tres chanchitos

[Música]

[Aplausos]

[Música]

eso tres chanchitos desobedientes sin el

permiso de su mamá una mañana muy

tempranito se salieron a pasear cuando

estaban paseando solos vino el lobo y se

los llevó los chanchitos lloran y dicen

ay señor lobo Ten compasión ya no

seremos desobedientes ayudaremos a mamá

tres chanchitos se van entren se van

entren se van

entren uno moviendo el loquitos otro

moviendo la patita otro moviendo la

colita tres chanitos se van en tren se

van en tren y muy

[Música]

bien tres chanchitos desobedientes sin

el permiso de su mamá Una mañana mu

tempranito se salieron a pasear cuando

estaban paseando solo vino el lobo y se

los llevó los chanchitos lloran y dicen

ay señor lobo Ten compasión ya no

seremos desobediente ayudaremos a mamá

tres chanchitos se van entren se van

entren se van

entren un movi bien veloci quito otro

Endo La Patita otro moviendo la colita

tres chanchitos se van en tren se van en

tren y muy

bien Eso

[Música]

[Música]

Eso than