¿P=NP? (1ª parte)

¿P=NP? es uno de los problemas más importantes de las matemáticas en la actualidad. Tiene, además, "peligrosas" implicaciones en el mundo en el que vivimos. Hace tiempo os propuse que intentaseis hacer a mano, en menos de 5 minutos, los siguientes cuatro problemas:

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.

Poyejali! (¡Vamos allá!, en ruso, pronunciado por Yuri Gagarin al despegar rumbo al espacio).

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 (no utilizo criterios de divisibilidad):

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 corto) décadas para hacer todas las cuentas.

Nacho, campeón del mundo de cálculo

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 es una amenaza!- 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).

Continuará...