Vinay Deolalikar y las clases de complejidad P y NP

Vamos a hablar de uno de los grandes problemas de la matemática y de la computación actual. Los «verdaderos» conceptos que entran en juego aquí son, en general, bastante técnicos, pero yo los ignoraré completamente para explicar para el amplio público de qué va este problema y qué es lo que Deolalikar parece haber resuelto.

Imaginaos que estamos trabajando en un hospital, y tenemos un gran catálogo desordenado de historiales de pacientes. Y nos piden que le demos el historial de un paciente concreto. Una forma muy sencilla que se nos ocurriría a cualquiera es buscar uno a uno, hasta encontrar el expediente pedido. En el peor caso, el paciente estará el último del catálogo. Por tanto, en el peor caso, habremos buscado en tantos expedientes como pacientes registrados existan en el hospital. Por ejemplo, como muestra la siguiente gráfica (de 1 a 1000 pacientes), si existen 100 pacientes en el hospital, tendremos que buscar sobre 100 personas, donde la persona 100 será nuestro particular enfermo. Si el hospital tiene 550 pacientes, pues 550 pasos, y así, tantos pasos como pacientes tenga nuestro hipotético hospital. Evidentemente, si tu paciente está entre los primeros durarás mucho menos, pero si tu catálogo está desordenado no puedes predecir dónde estará el siguiente que tengas que buscar.



Cuando estemos aburridos de enfrentarnos al mismo trajín de buscar decenas de clientes cada día con este torpe pero único método posible, se nos puede ocurrir ordenar a todos los pacientes, ya que, con los pacientes ordenados, se podría tardar en encontrar a cualquier paciente particular en muy poquitos pasos. Ahora, ¡ordénalos! Con el mejor método conocido para ordenar pacientes, a medida que aumenta el tamaño del problema, el número de pasos necesarios para hacerlo crece de la forma que expresa la siguiente gráfica (en color verde):



En esta gráfica hemos acompañado la gráfica anterior (color rojo), para poder compararlos. Vemos como, para 500 pacientes, frente a los 500 pasos necesarios para la búsqueda, la ordenación «cuesta» unos 3.000 (6 veces más). Y para 1.000 pacientes, hacen falta unos 7.000 pasos para ordenarlos (7 veces más). Si fueran un gran número de pacientes, pongamos 10.000, harían falta unos 40.000 pasos, y no creo que nadie tenga ganas de perder varias mañanas de su tiempo en hacerlo. Si el número de pacientes fuera 100.000, necesitarías perder semanas o incluso meses. Pero aún así, un buen ordenador lo haría en menos de un segundo (si los historiales estuvieran digitalizados). En resumen, lo que antes era solamente buscar en un conjunto de datos desordenado, ahora queremos ordenar dicho historial, para que la búsqueda sea mucho (mucho) más rápida. El inconveniente es que la ordenación es mucho más costosa que la búsqueda, y la ventaja es que ordenar un historial solamente se hace una vez, reduciendo considerablemente, a partir de entonces, el tiempo necesario cada vez que tengas que volver a buscar (y seguro que esto ha de hacerse muchas más veces).

A este concepto acerca del «número de pasos» de un método (con muchas precisiones más en las que no entraremos) se le conoce como "órden asintótico de un algoritmo" (un algoritmo es más o menos lo que todos entendemos como método). De los distintos métodos que puedan existir para resolver un mismo problema, los informáticos intentan buscar aquel que necesite un número menor de pasos para resolverlo. Así que la «dificultad» de un problema, depende ampliamente de los métodos encontrados para resolverlo. Si se encuentra un buen método, que lo resuelva en poquitos pasos, podremos decir que el problema es «sencillo» de resolver.

Imaginemos ahora otro problema, mucho más complejo (incluso para un ordenador), consistente en un trabajador, un viajero, o cualquier persona que necesite ir a una serie de ciudades (empezando por una en concreto, y terminando por otra en concreto), pero queriendo minimizar sus gastos. Lo que tiene que hacer este hombre es buscar, de entre todos los caminos y carreteras posibles, el camino cuya distancia en kilómetros sea menor, y evidentemente, pasando por todas las ciudades que él desea visitar (y sin pasar dos veces por la misma).



En la imágen anterior se ve una representación de un posible conjunto de ciudades, con todas las carreteras posibles existentes. En la imágen que viene a continuación, se ve la gráfica del número de pasos necesarios para resolver el problema, a medida que aumenta su tamaño (número de ciudades), junto a las dos gráficas anteriores, para observar las diferencias.



Vemos como en este último caso (gráfica azul), las dos gráficas anteriores quedan completamente absorbidas, debido al alto coste asociado con éste método de búsqueda, y eso que solo hemos puesto la gráfica hasta problemas de tamaño 10. Si pusiéramos gráficas hasta problemas de tamaño 1.000, como en las gráficas anteriores, las gráficas roja y verde no se verían en el gráfico.

El por qué de este coste tan alto es debido a un fenómeno llamado "explosión combinatoria". Con el solo hecho de añadir una ciudad más (imaginando que existe una carretera entre cualquier par de ciudades), el número de caminos posibles se dispara. Y al poner otro más, el número de caminos nuevos es incluso mayor que el incremento anterior. Por ejemplo, con cinco ciudades hay 6 caminos posibles. Pero con siete solo hay 120 cuando con ocho hay 720. Con diez, más de 40.000 caminos. Con 20 caminos, para encontrar el camino más corto entre más de 6.000 billones (con b) de caminos hace falta más de 70.000 años de cómputo. Con 100 ciudades (que no son tantas), el número de años necesarios sencillamente no cabe en la calculadora (del portátil) que utilizo para mis cálculos.

Aunque este problema parezca infantil, ejemplifica muy bien a todos los problemas que sufren dicha explosión combinatoria. Este tipo de problemas se usan, por ejemplo, en seguridad informática. Para cifrar mensajes se acuden a situaciones donde un intruso que desee descifrarlos necesite realizar una búsqueda que duraría millones de años.

La clave está en la forma en que crece el número de pasos necesarios para resolver el problema. A los que crecen de una forma tratable (como los dos métodos enunciados al principio, el de la búsqueda y ordenación de clientes de un hospital), se les llama (muy -muy muy- grosso modo) problemas P. Los problemas intratables (como el problema del viajero, que presentan explosión combinatoria) se denominan NP. Existen muchas más clases de complejidad, así como también existen muchos tipos distintos de problemas, cada uno con sus propias limitaciones. Aquí solo hemos expresado las limitaciones en tiempo, pero también hay problemas que sufren los mismos problemas de espacio (cantidad de memoria necesaria para guardar los datos requeridos en el cálculo de la solución del problema).

La cuestión es si un problema NP es «esencialmente NP», o es que todavía no hemos encontrado un método tratable para resolverlo. La opinión generalizada es que los problemas NP, son «esencialmente intratables», es decir, que los métodos para resolver los problemas NP se comportan como el problema del viajero, y es imposible que exista un método que no lo haga de esta forma.

Este problema es uno de los siete problemas del milenio, propuestos por el instituo Clay de Matemáticas, con un premio de 1 millón de dolares a quién lo resuelva, y de ahí la gran cantidad de intentos por resolverlos, algunos que rozan el fraude. Pero Vinay Deolalikar cree haber resuelto el problema, o al menos, su investigación y su trabajo parece bastante serio, y llega a la conclusión que todos esperaban: los problemas NP, son efectivamente, problemas NP.

La noticia ha sido filtrada por Internet. Vinay Deolalikar es un trabajador de la empresa HP que dedicó sus tiempos libres a dedicarse al estudio e investigación sobre éste problema, y que duró varios años en preparar ésta demostración , y que, por supuesto, mantuvo en secreto. Ha hechado mano de muchos elementos de varias ramas de la matemática y de algunos resultados de la física estadística para construir esta demostración, que, junto a un resumen de la historia del problema y de su propia demostración, tiene una longitud total de unas 100 páginas.

Vinay Deolalikar aún no había publicado su demostración formalmente, pero un colega al que Deolalikar envió un correo junto con su demostración, lo publicó en su propio blog, y luego se terminó de expandir por Internet. Debido a que la demostración de Vinay aún no ha sido contrastada ni verificada por la comunidad de matemáticos, no tenemos garantías para afirmar que esta demostración constituya una demostración definitiva o fiable, y tampoco podemos, por tanto, afirmar que los problemas NP sean esencialmente intratables, pero varios expertos ya han defendido la seriedad del trabajo. También se comenta que, debido a que ésta demostración usa resultados que pertenecen al campo de la física y no de la matemática pura, quizás no supere el exámen de rigor exigido para que la prueba sea anunciada como legítima y de total garantía.

NOTA (17/02/2014): Debido a un amable comentario de un lector, exigiendo una corrección ortográfica (muchas gracias por el aviso), aprovecho para decir que, a los pocos meses de la publicación, expertos en el campo han rechazado la demostración por contener algunos fallos importantes, siendo la demostración, por tanto, falsa; incluso se llegó a crear un wiki para comentar y analizar la demostración. Aunque se afirmó que Vinay volvió a trabajar en la demostración para pulirla y perfeccionarla, los expertos no creen que el camino seguido en la demotración llegue a ningún resultado interesante.