¿Comprobar o resolver? Esa es la cuestión. ¿P=NP?

¿De qué va esta entrada? 

 Teniendo en cuenta que el título es bastante explícito tan solo diremos que está en nuestro ánimo aclarar de la forma más exquisita posible el problema P/NP.  

Somos conscientes de que se han escrito miles de palabras sobre el tema a nivel de divulgación y popularización. 

 Desgraciadamente, también somos conscientes de que un alto porcentaje de las mismas son mamarrachadas de un considerable calibre.  

Esperamos con anhelo no formar parte de ese excelso conjunto con esta, nuestra pequeña contribución.

El problema que pretendemos desgranar es bello, es hermoso, es complicado y es esencial para la matemática y para la física. 

Su solución en un sentido u otro, y aclararemos eso en esta entrada, supondrá una demostración de que hemos entendido algo del universo o bien que no habíamos entendido nada pero que será fácil empezar a entenderlo todo. (Estamos siendo crípticos en pleno uso de nuestras facultades mentales).  Vamos a establecer qué es eso del problema P/NP.

Vamos al lío… Nunca mejor dicho.

Comprobar y resolver no parecen lo mismo pero tampoco lo sabemos seguro

¿Qué te parece más fácil?  

Que te den un sudoku gigante y te pidan que lo resuelvas o que te den el mismo sudoku relleno de números y te pidan que compruebes si está bien resuelto.

Resuelve:

Comprueba:

No sabemos qué pensarán, pero nosotros tenemos la intuición de que es más fácil comprobar que resolver.  Esto en mates suele ser bastante más hiriente.  En general, tenemos la sensación de que es mucho más fácil comprobar si algo que te dan es solución de un problema que encontrar una solución al problema por ti mismo.  Por ejemplo, es más fácil comprobar que x=5 resuelve la ecuación x^2+x-30=0 que encontrar la solución por nuestros propios medios. 

 Las cosas se pueden poner muy feas en matemáticas.

Pero, ¿es más fácil comprobar que resolver? ¿Seguro?  

Que nos parezca más fácil comprobar que resolver no significa que eso sea lo correcto.  Especialmente cuando tratamos con gentes de matemáticas, porque ya sabéis:  Esto es matemática y aquí hay que demostrar.  

 De todas formas nosotros no confiaríamos ni un pimiento en nuestra intuición, por poner un ejemplo, la materia nos parece continua y sabemos que en realidad es un puñado de átomos muy lejos los unos de los otros en relación a los tamaños típicos de los átomos. 

La materia de continua tiene poco. 

Resolver o comprobar es cuestión de tiempo

Vamos a entrar en harina, dijo el caracol (chiste autóctono de la zona donde los autores crecieron y que es graciosísimo porque los caracoles se meten en harina para secarles las babas antes de empezar a cocinarlos) y vamos a hablar de complejidad computacional.

El campo de la complejidad computacional enmarca su campo de aplicación a la clasificación de los distintos problemas en función del tiempo que tardamos en resolverlos con un algoritmo o receta matemática diseñada para tal efecto.

  Es un campo ciertamente complejo que tiene sus raíces en la lógica, la combinatoria y los fundamentos más básicos de la matemática como llegaremos a intuir en el transcurso de esta compleja entrada (otro chiste). 

 Nos podríamos poner muy formales pero la verdad nos quedaría una cosa bastante pedante.  Por el bien tanto de nosotros como autores como de vuestras mercedes, lectoras y lectores de esta entrada, vamos a procurar simplificar la palabrería propia del tema procurando en todo momento no decir nada que roce lo absurdo o incorrecto.

Centremos el tema…

Supongamos que tenemos un problema y un algoritmo para él, es decir, una receta de pasos que si los seguimos encontramos una solución al problema.  La situación no puede ser más idílica.

  ¿Qué podemos pedir más?  Si tenías un problema y has encontrado un algoritmo que lo resuelve ya no hay problema del que preocuparse.

Ese es el caso hasta que llega la típica persona que hace la típica pregunta incómoda. En esta situación la pregunta es:

¿Cuánto tarda el algoritmo en encontrar la solución?

-Uuupsss-, es lo primero que a cualquiera se le vendría a la cabeza para esa pregunta.

Se puede dar el caso de que tengamos un algoritmo que encuentre la solución pero que el tiempo que tarde en encontrarla sea tan alto que a efectos prácticos no tenemos solución alguna. 

 Imagina que tu algoritmo necesita varias veces el tiempo de vida del universo en encontrar la solución, ciertamente es un algoritmo poco operativo.

Otra pregunta que nos puede poner en un brete es: 

 ¿De qué tiempo hablas cuando hablas de tiempo en este contexto? 

 Y esa es una muy buena pregunta porque para resolver el problema se lo tenemos que dar a una máquina en la que hemos programado el algoritmo y que ejecuta los pasos del mismo haciendo las operaciones necesarias para llegar a dar una respuesta. Es evidente que no es lo mismo usar un spectrum que un supercomputador o tu propia cabeza.  Cada uno en función de su hardware o el lenguaje de programación elegido tardará más o menos.

Aquí lo interesante es trabajar con generalidad sin comprometernos con una máquina concreta o un lenguaje de programación concreto.  

Así establecemos que el tiempo que tarda un algoritmo en realizar su tarea como el número de operaciones necesarias para finalizar su trabajo y dar una respuesta.  Evidentemente si nuestro supercomputador resuelve un problema en segundos, el spectrum podrá tardar una semana, un mes o años, pero es un tiempo manejable.  Si el supercomputador necesita el tiempo de vida del universo para solucionar un problema…

Por lo tanto, el tiempo asociado a un algoritmo es el número de operaciones que ha de realizar para resolver un problema.

 A eso se le denomina complejidad del problema.

La complejidad no hace referencia a lo fácil o difícil que sea resolver el problema en términos coloquiales sino a la que hay que liar, el número de operaciones necesarias, para resolverlo.  En realidad, el problema está resuelto teóricamente, tenemos un algoritmo que lo hace, el tema es cuánto tiempo tardará en hacerlo, es decir, cómo de complejo es llegar a la solución.

Detente un segundo a recapacitar sobre lo que llevamos y prométenos que no seguirás leyendo hasta que tu cabeza esté convencida de haber pillado estos detallitos.  Mientras haremos un comentario para los tiquismiquis.

Nota para exquisitos:

  Sí, lo sabemos, aquí podríamos haber sacado las plumas de pavo real y meternos a discutir sobre la notación de Landau, asintotismos (sí, también sabemos que no existe esa palabra, pero ahora ya sí existe) varios y cotas inferiores y superiores.  

El tamaño importa

Vamos a empezar por un ejemplo sencillo. 

 Esto va de multiplicar números.

Caso 1:

Suponte que te piden encontrar la solución al problema 5 x 7.  Este es un problema matemático del que tenemos un algoritmo, al menos uno, para encontrar una solución.  Eso requiere una operación.

Ahora imaginemos que nos piden resolver el problema 23 x 19.

  Eso sí, ahora requerimos cuatro operaciones (sólo contamos las multiplicaciones que hemos de realizar, también hay que hacer unas cuantas sumas pero consideramos que eso no cuesta tiempo de cálculo comparado con las multiplicaciones).

¿Cuántas operaciones necesitamos para multiplicar dos números de 3 cifras? 

¿Y de 4 cifras?  Está claro que empleando el algoritmo que nos enseñan en los coles tendremos que realizar 9 y 16 operaciones respectivamente.

Así, podemos decir que el algoritmo de multiplicación (para números del mismo número de cifras en este caso) tardará más o menos dependiendo del tamaño de los números iniciales que queremos multiplicar.

Cuando hablamos del tiempo que tarda un algoritmo en resolver un problemas hemos de referirnos al número de operaciones necesarias en función del tamaño de los datos de entrada del problema.

P y NP

Es hora de entrar en el meollo de la cuestión. 

P y NP son etiquetas que les asignamos a los problemas.  Estas etiquetas no están relacionadas con “se puede resolver” y ” no se puede resolver”.  

Eso tiene que quedar claro.

Vamos a definir estas etiquetas de los problemas:

Problemas tipo P

Diremos que un problema es de tipo P cuando conocemos un algoritmo que lo resuelve en tiempo de la forma  siendo k un número positivo.

 Eso se dice tiempo polinómico o complejidad polinómica.

Es decir, los problemas P son aquellos que se pueden resolver en tiempo razonable.  Hay que hacer un número de operaciones que crecen lentamente, polinómicamente para ser estrictos, con el tamaño del dato de entrada.

Problemas de tipo NP

Diremos que un problema es de tipo NP cuando conocemos un algoritmo que es capaz de comprobar si algo dado es solución del problema en un tiempo polinómico.

Vamos que los problemas NP son aquellos para los que podemos comprobar si algo es solución en tiempo razonable dependiendo del tamaño de la solución propuesta.

Eso no quiere decir que no exista un algoritmo que los resuelva en tiempo polinómico.  Lo que quiere decir es que no sabemos si existe o no, ese es el problema realmente.

Ahora viene un detalle esencial… abran bien los ojos y las cabezas.

Todos los problemas P son NP

¡Evidentemente!, habrás pensado.  Si los problemas P  son aquellos para los que tenemos un algoritmo que los resuelve en tiempo razonable (polinómico) es lógico que podamos comprobar si algo es solución en tiempo razonable, el propio algoritmo que lo resuelve es un ejemplo. 

 Tú nos das una solución, nosotros corremos nuestro algoritmo y nos da una respuesta en un tiempo razonable, comprobamos si la solución del problema es la que tú nos has dado o no lo es.  Por tanto hemos comprobado si algo es solución en tiempo polinómico.

Pero dado que los problemas para los que podemos comprobar si algo es solución son los problemas NP entonces todos los problemas P son NP por derecho propio.

Podemos representar esto usando diagramas de conjuntos:

Es decir, los problemas que podemos resolver en tiempo razonable están incluídos en los problemas que podemos comprobar si algo es solución en tiempo razonable.  

Los problemas P son problemas NP.

Vayamos al problema de verdad, ¿P=NP?

Muchas veces se dice que los problemas P son los que se pueden resolver y los problemas NP son los que no se pueden resolver.

Si esa es la definición hemos demostrado ya que P no es igual a NP, fin de la historia.  Si unos se pueden resolver y otros no entonces se ha acabado el juego.

El problema es que hay problemas NP que no sabemos si admiten un algoritmo que los resuelva en tiempo razonable, es decir que sean en realidad de la subclase P.    Hay muchos problemas NP para los que se conocen algoritmos para resolverlos solo que no dan la respuesta en un tiempo razonable.  

Puede que todos los NP se puedan resolver en tiempo razonable y puede que no.  Eso es justamente lo que se nos plantea.

Las situaciones que podemos tener son:

a)  Que P no sea igual a NP.  Resolver no es igual a comprobar.

b) Que P y NP sean iguales.  Resolver y comprobar son igualmente de complicados.

Para demostrar que P y NP no son iguales bastaría con mostrar que un único problema de tipo NP no admite un algoritmo que lo resuelva en tiempo polinómico.

Claro, para demostrar que todos los problemas NP son P tendríamos que encontrar para todos y cada uno de ellos un algoritmo que los resuelva en tiempo polinomial.  Eso es mucho trabajo.

Pero en realidad hay un detalle mágico en todo esto…

Problemas NP-completos

De entre todos los problemas NP, los que podemos comprobar si algo es solución en tiempo polinómico pero no sabemos si podemos resolverlos en tiempo polinómico o no, hay unos que pertenecen a una clase especial, los NP-completos.

Un problema NP es NP-completo si por un lado es NP, evidentemente, y además si cualquier problema NP se puede traducir, (el término técnico es reducir) a ese problema NP concreto.

La sorpresa llegó en la década de los 70 del pasado siglo cuando se demostraron unos teoremas que establecen la existencia de estos problemas NP-completos.  

Demostraron que cualquier problema NP se podía reducir o traducir, como prefieras a un problema NP-completo y demostraron que los problemas NP-completos eran todos equivalentes entre sí.

Dado que cualquier problema NP se puede reducir a un problema NP-completo y todos los completos son equivalentes resulta que:

1.-  Si alguien demuestra que un problema NP-completo no admite un algoritmo que lo resuelva en tiempo polinomial habrá demostrado que P es distinto de NP.

2.-  Si alguien demuestra que un problema NP-completo se puede resolver con un algoritmo en tiempo polinomial, es decir, que ese problema en realidad es P, habrá demostrado que P es igual a NP.

Si demuestras lo primero dirígete al Instituto Clay y diles que has resuelto uno de los Problemas del Milenio.  Ganarás un millón de dólares, la fama y la inmortalidad en el universo de las matemáticas.

Si demuestras que P=NP tendrás acceso a cualquier sistema informático, a cualquier tarjeta de crédito, a cualquier dato que quieras, a cualquier cuenta bancaria, a cualquier información.  

Eso es porque el sistema de encriptación que tenemos en la actualidad se fundamenta en la creencia de que resolver es más difícil que comprobar. Las claves son números enormes que hay que descomponer en números primos.  Más o menos, no sabemos si ese problema se podría hacer en tiempo polinomial pero actualmente no hay algoritmo que lo consiga. 

 Sin embargo, si conoces los números primos grandes es fácil multiplicarlos para ver si reproducen la clave.  Basta multiplicarlos y listo.

Pero ojo, no vayas al Instituto Clay, no se lo digas a nadie porque lo más seguro es que te quiten de la vista.  Es más barato matarte que cambiar todo el chiringuito que tenemos montado.

Nos seguimos leyendo…