Los problemas P son aquellos para los que CONOCEMOS un algoritmo que permite resolverlo rápidamente.
Los problemas NP son aquellos para los que CONOCEMOS un algoritmo que permite resolverlo... pero en realidad casi nos da igual porque tardaríamos muchísimo tiempo en hacerlo. Es como si en la práctica fuesen imposibles de resolver.
Y la palabra clave es ese CONOCEMOS: podemos preguntarnos, para los problemas NP, ¿no existirá un algoritmo más rápido y lo que pasa es que todavía no lo hemos descubierto? Dicho de otra forma, ¿no será que los problemas NP son en realidad problemas P, pero todavía no lo sabemos? Más corto: ¿P=NP?
Vamos terminando:
¿Cuál se cree que es la respuesta? La inmensa mayoría de los matemáticos piensa que no, que para los problemas NP no existen algoritmos mejores a los que ya conocemos, que P no es igual a NP. Pero... René Descartes, uno de los mejores matemáticos de la historia, dijo que la mente humana nunca conseguiría resolver algunos problemas... que ahora sabe hacer cualquier buen alumno de bachillerato de ciencias.
¿Y esto sirve para algo, tiene alguna utilidad? Los problemas NP son la base de la criptografía (que es la codificación de la información para que no pueda verla nadie más que quien la envía y quien la recibe). Teniendo en cuenta que nuestras comunicaciones y nuestra actividad financiera están completamente informatizadas, que sean seguras depende de que los problemas NP sean prácticamente imposibles de resolver.
Cuando Eduardo emplea la palabra "imposible" debería decir, "imposible siempre y cuando NP no sea P". Acabo de mirarlo y un bitcoin (la moneda de la que habla en el vídeo) vale ahora mismo unos 6500 euros. En el mismo momento en el que alguien descubriese algoritmos rápidos para los problemas NP (es decir, que P=NP) el valor de un bitcoin sería exactamente 0 euros.
¿Y si los problemas NP no son P, como parece que es, todo está tranquilo? Pues esto todavía se complica un poco más porque hay otra amenaza en el horizonte: los ordenadores cuánticos.
¿Ordenadores cua.. qué? Recordad que la física cuántica es rara, rara, rara...
Bueno, pues parece que vamos a poder aprovechar estas "cosas raras" para construir ordenadores "infinitamente" más rápidos que los que tenemos en la actualidad. Por seguir el ejemplo de la minería, un ordenador actual es un pico y una pala, y un ordenador cuántico va a ser una perforadora capaz de "llegar al centro de la tierra". Copio y pego el párrafo de una noticia que leí hace poco:
En 2015 la Agencia Nacional de Seguridad (NSA) de EE UU anunció que los estándares actuales de criptografía de clave pública no son seguros a largo plazo y pidió que se iniciara cuanto antes la búsqueda de algoritmos de cifrado de clave pública seguros contra ordenadores cuánticos, también llamados postcuánticos.
Vamos a resolver los cuatro problemas que os propuse en la anterior entrada dándonos cuenta de una característica que tienen en común (y también nos fijaremos en lo contrario, en qué son diferentes):
En los problemas 1 y 3 nos piden dividir dos números entre 7. Ya hace muchos años que os enseñaron el algoritmo de la división, es decir, el procedimiento que hay que seguir cuando uno quiere dividir dos números. Relojes a cero y ¡adelante!
En los problemas 2 y 4 nos piden que comprobemos si dos números son primos. Si recordáis, en la 1ª evaluación vimos el algoritmo que nos permitía hacer dicha tarea: comprobar si el número que nos dan es divisible (o no) por todos los números primos hasta su raíz entera. A ver cómo se me da:
Y ¿es 2305843009213693951 primo? Pues la verdad es que, a mano, Nacho, que parece que calcula "algo mejor" que yo, necesitaría (me invento la cifra y seguramente me estaré quedando muy corto) décadas para hacer todas las cuentas.
Conclusiones:
Sabemos resolver los dos problemas (dividir un número por otro y comprobar si un número es o no primo) ya que conocemos los métodos (algoritmos) para hacerlo. Sólo es cuestión de tiempo.
Cuando aumenta el tamaño del número uno de los problemas (dividir) sigue estando muy a tiro pero el otro (comprobar si un número es primo) enseguida se nos escapa de las manos a poco grande que sea el número.
Ya podemos entender lo que es P y lo que es NP.
En matemáticas los problemas P son aquellos para los que conocemos un algoritmo que se puede hacer en un tiempo razonable incluso para números grandes, mientras que los problemas NP son aquellos para los que conocemos un algoritmo, pero el tiempo que nos costaría aplicarlo es exagerado en cuanto el número aumenta un poco.
Notas finales:
P significa tiempo polinomial y NP tiempo no polinomial (aunque podría, no os voy a explicar ahora de dónde viene el nombre; cuando en 4º de ESO os presenten las funciones exponenciales le preguntáis a vuestro profesor por esto).
Os podéis imaginar que hoy en día los algoritmos no se hacen a mano sino con máquinas. Evidentemente los ordenadores son rapidísimos pero la idea no cambia: los problemas P son aquellos que un ordenador hace “rápido” y los NP aquellos para los cuales tardaría años (o décadas o siglos o...) en resolver, por mucho que mejoren los ordenadores.
Lo que acabo de decir no es del todo cierto. Os lo cuento... ¡en la última entrega! (Hay un término inglés para esto de cortar en un momento emocionante: cliffhanger).
¿Con qué sueña un matemático? ¿Cómo se gana la inmortalidad? Esencialmente siendo el primero "en cazar una gran presa", en resolver alguno de los grandes problemas de las matemáticas.
¿Cuáles son esos problemas? En el Congreso de París del año 1900 David Hilbert, el matemático más destacado de la época, propuso su famosa lista con los 23 problemas que se consideraron los más importantes del siglo XX.
En el año 2000, la Unión Matemática Internacional, que aglutina las Academias de Matemáticas de aquellos países que tienen Academia de Matemáticas, hizo una "repetición de la jugada" creando la
y el Clay Mathematics Institute (una organización fundada por un millonario aficionado a las matemáticas) ofrece un millón de dólares a quien resuelva alguno de los
¿De qué van esos problemas? Voy a intentar contaros algo de uno que aparece en las dos listas, el ¿P=NP?, y para eso necesito que antes resolváis los siguientes cuatro problemas a mano.
Importante: para cada uno de ellos tenéis como mucho 5 minutos.
Problema 1: divide 23 entre 7.
Problema 2: comprueba si 23 es un número primo.
Problema 3: divide 2305843009213693951 entre 7.
Problema 4: comprueba si 2305843009213693951 es un número primo.
Y os lo estoy diciendo a todos. Este mes que nos queda vamos a hacer dos cosas:
1) Repasar para preparar los exámenes de recuperación. Cuento con la colaboración de los que ya habéis aprobado para ayudar a vuestros compañeros.
2) Además, "en paralelo", en 1º de ESO vamos a ver Estadística y Probabilidad y, en 2º de ESO, Probabilidad. Aquí os cuelgo las diapositivas que utilizaremos en clase:
Y para abrir boca quiero que me contestéis a estas dos preguntas:
1) Tengo una moneda legal (la he probado un montón de veces y sale cara la mitad de los lanzamientos y cruz la otra mitad; no exactamente, pero vamos, aproximadamente la mitad de cada). La lanzo 6 veces y salen 6 caras seguidas (no es lo más habitual pero puede ocurrir). La voy a lanzar una séptima vez. ¿Qué creéis que es más probable que salga, cara o cruz?
2) Tengo una moneda y no tengo ni idea de si es legal o está trucada. La lanzo 6 veces y salen 6 caras seguidas. La voy a lanzar una séptima vez. ¿Qué creéis que es más probable que salga, cara o cruz?
