Pablo Brenner & Sergio Fogel Blog

La teoría de la complejidad (Complexity Theory) es posiblemente una de las ramas más complejas de la matemática. Esa rama estudia la complejidad de los problemas de computación: qué problemas son inherentemente complejos, tan complejos que el tiempo que se demora en resolverlos crece enormemente a medida que la cantidad de datos aumenta. Por ejemplo, el problema de ordenar un conjunto de números es un problema fácil. Si me dan el doble de números, el tiempo que demora ordenarlos es apenitas más que el doble. En cambio, el problema de encontrar el camino óptimo para que un vendedor visite un grupo de ciudades es un problema complejo. No se conoce ninguna solución «rápida», es decir, en la que el tiempo que demora crece linealmente con la cantidad de datos.  Es peor aún, no se conoce ninguna solución en la que el tiempo crece con el cuadrado de la cantidad de datos, ni con el cubo, etc.

Uno de los problemas abiertos hace más tiempo en la teoría de la complejidad, es si los problemas como el del vendedor viajante son inherentemente complejos. Es decir, la pregunta es si jamás encontraremos una manera de resolver esos problemas en tiempos polinomiales.

Esa pregunta se resume en una simple fórmula: saber si P es diferente de NP. Y esa pregunta está abierta desde hace más de 40 años. En realidad todo el mundo intuye que P es diferente de NP, pero no hay ninguna demostración matemática. En mis épocas del master dediqué una cuantas horas a tratar de acercar aunque sea algún milímetro la solución de ese santo grial. Gente mucho más inteligente, mejor formada y más experiente le dedicó su vida al tema. Pasaron las décadas, y nada. Hasta ahora.

Vinay Deolalikar, un científico de origen Indio que trabaja en HP,  publicó esta semana un paper donde aparentemente demuestra que P es diferente de NP. Digo aparentemente, porque el paper es de más de 100 páginas, y no es nada fácil de comprender. Habrá que esperar la opinión de los demás investigadores del campo. Si el paper es correcto sería el avance más importante en la historia de la teoría de la computación. Es un resultado comparable al teorema de Fermat, que estuvo más de un siglo esperando la solución, o a la conjetura de Poincaré. Es uno de los Problemas del Milenio: los siete problemas más importantes sin solución. De los siete quedan seis, el séptimo lo resolvió el ruso Grigory Perleman.

Un dato interesante es que otro problema abierto desde hace mucho tiempo (sobre la complejidad de saber si un número es primo), fue resuelto hace cerca de 10 años por dos estudiantes de doctorado de la India y su tutor. Cuando fueron a presentar sus resultados en EEUU, les negaron la visa.

Personalmente soy escéptico acerca de la validez de demostración. No porque la haya leído, no estoy en forma ni para intentarlo. Tal vez porque tengo la falsa creencia de que esos problemas quedan abiertos por siempre. Tal vez porque siempre lo vi como algo tan complejo que está más allá de la capacidad de cualquier ser humano. Tal vez porque alguna vez lo intenté y no lo logré.

Cual es el impacto para nuestras vidas? Eso es lo más claro de todo: no habrá impacto ninguno. Lo lamento.