¿Qué es eso de que “P ≠ NP”?

El post de hoy es una colaboración junto con Héctor (a.k.a. Hekanibru) ya que estamos iniciando un nuevo proyecto juntos. Se trata de un nuevo blog, Pedazos de Carbono, en donde ambos vamos a estar publicando durante toda la semana notas de ciencia, filosofía y más. Si les late la idea no duden en ir al nuevo blog y subscribirse o, si lo prefieren, nos pueden seguir en Facebook.

Homero 3D en Los Simpsons

Si tienen amigos que estudian o trabajan en el área de computación, probablemente la semana pasada se encontraron con algunas noticias comentando que si “P”, que si “NP”, o que si más bien la verdad “N.P.I.” ¿De qué se trata eso? ¿De qué estaban hablando? ¿Y a qué vino tanto alboroto?

El alboroto vino porque Vinay Deolalikar—un investigador de HP labs—publicó un manuscrito (¡de más de 100 páginas!) en donde clama haber resuelto uno de los problemas abiertos, seguramente el más conocido y más importante de todos, en el área de computación teórica. Él dice tener una prueba de que “P ≠ NP” y, si su demostración es correcta, además de quedar inmortalizado en la historia de la computación recibirá también un millón de gracias dólares por parte del Clay Mathematics Institute como premio por haber resuelto uno de los Problemas del Milenio.

Desde el principio se observó que el trabajo de Deolalikar es un intento serio de resolver este problema y que, en efecto, descubre una serie de conexiones súper interesantes entre áreas tan diversas como la física estadística, lógica proposicional, probabilidad, y teoría de cómputo. Sin embargo, para su infortunio, las últimas noticias parecen indicar que su demostración tiene varios errores más o menos graves y no funciona al menos sin hacerle algunas fuertes correcciones o añadiendo nuevas ideas.

Pues qué mala onda, pero ¿de qué se trataba el problema o qué onda? Ha de estar bien fumado, ¿no?

Pues puede parecer medio fumado o abstracto, pero la verdad es que la pregunta que Deolalikar trataba de responder—y muchos otros investigadores antes que él—tampoco es que sea una cosa así super marciana que sólo cerebros superdotados puedan entender. La pregunta, de hecho, es relativamente sencilla.

Los teóricos de la computación clasifican los problemas que tratan de resolver según qué tan “complejos” son. P y NP son precisamente dos de estas clases en las que agrupan problemas, y se sospecha que los problemas que pertenecen a P son relativamente más “fáciles” que los que pertenecen a NP. Pero vamos a ver, ¿qué significa todo esto?

Sudoku en Wikipedia

¿Conoces el Sudoku? Seguro has visto esos jueguitos; traen una cuadrícula en la que están escritos algunos números y tu tarea es llenar los cuadritos vacíos siguiendo algunas reglas (por ejemplo que no se repitan números en un mismo renglón, etc.). Si has tratado de resolver uno, sabes que tienen su chiste, quizá a veces tienes que “adivinar” algunos de los números y—si te das cuenta que cometiste un error—regresar, borrar los números que están mal, e intentar de nuevo.

Pero ahora imagina que te doy un Sudoku ya con todos los cuadritos llenos y lo único que te pido es que verifiques si, según las reglas del juego, mi solución es correcta. ¡Eso es mucho más fácil! Lo único que tienes que hacer es, por ejemplo, ir renglón por renglón verificando que no hayan números repetidos y así comprobar que todas las reglas se cumplan. Ahora, ¿has visto esos mega-Sudokus? Si consideramos Sudokus más y más grandes, seguro te vas a tardar más y más tiempo en verificar si mi solución es correcta. Pero aquí la clave está en que el tiempo que te vas a tardar en verificar la solución tiene una relación muy particular y directa con el tamaño del Sudoku que yo te dé. Los computólogos, de hecho, dicen que el problema de verificar soluciones del Sudoku está en la clase P, ya que el tiempo que te tardarías en realizar esa tarea se puede expresar como un Polinomio que depende del tamaño del Sudoku en cuestión.¹

Por otra parte, el problema de resolver un Sudoku—el original donde tú tienes que tienes que llenar los cuadritos—es un problema que está en NP. Aquí NP significa “No determinista Polinomial” y es una manera rebuscada que los teóricos tienen de decir: “se vale que intentes todas las posibles soluciones una tras otra, por ensayo y error, siempre que verificar si una solución es correcta sea un problema en P”. Esto de hecho te sugiere un método, aunque un poco “bruto”, para resolver los Sudokus: intenta una tras otra toda las posibles soluciones y luego verifícalas hasta que te encuentres la correcta. Sin embargo, el tiempo que te vas a tardar siguiendo este método se “dispara” de manera exponencial respecto al tamaño del Sudoku. Pero si recuerdas tus clases de álgebra, ¡las funciones exponenciales no son polinomios! Esto parece sugerir que los problemas en NP son, de algún modo, más difíciles que los de P.

Pero justo esa es la pregunta del millón (¡literalmente millón de dólares!), ¿será que los problemas en NP son en efecto más difíciles que los que están en P? Dicho de otro modo, ¿es cierto que buscar soluciones a un problema es realmente más difícil que verificar soluciones de ese mismo problema? Y puede parecer increíble, pero este problema sigue abierto desde hace casi 40 años cuando a Stephen Cook se le ocurrió por primera vez.

La intuición parece decir que, ¡claro! buscar soluciones es más difícil que simplemente verificarlas. Sin embargo, aun con todo el conocimiento de cómputo que tenemos hasta ahora, no hemos podido descartar la posibilidad de que algún día a un programador brillante se le ocurra un método súper original que pueda resolver problemas como el de Sudoku en un tiempo polinomial.

Sin embargo lo que la mayoría de los computólogos piensan, y es lo que Deolalikar pensó que había demostrado, es que las clases de “P” y “NP” son diferentes. Es decir, hay problemas para los que buscar soluciones (no importa cuántos programadores brillantes tengas) siempre va a ser más difícil que verificarlas.

¿Ves? Al final toda esta cuestión “fumada” se pudo explicar con Sudokus. Ahora sólo resta ver qué va a suceder con la dichosa “prueba” de Deolalikar. ¡Hagan changuitos!

Hekanibru y Juan.

¹ Para ilustrar qué significa esto, imagina que dado un Sudoku lleno de n×n (ó n²) cuadritos, tú te tardarías, digamos, unos 3n² minutos en verficarlo. Dado que pudimos expresar la formulita del tiempo como un polinomio (3n²) que depende del tamaño del Sudoku (n²), ¡tenemos un problema en P!

Directo desde Pedazos de Carbono.