[cerrar]

Comparta esta nota con un amigo

E-Mail de su amigo
Su nombre
Su E-Mail

Hace muchos años que escribo sobre matemática y, más allá de hacerlo en forma pública, estoy involucrado con esta ciencia desde 1964, año en que empecé a cursar las primeras materias de lo que entonces era el Curso de Ingreso y hoy se llama CBC. ¿Por qué cuento esto? Porque nunca tuve un desafío semejante como el que quiero abordar ahora. Quiero contar una de las historias más apasionantes de la matemática, que involucra un problema que lleva más de 40 años desde su presentación y no sólo no tiene solución, sino que no está claro que la vaya a tener mientras usted y yo vivamos. No sólo eso: como el problema plantea una pregunta, si la respuesta fuera afirmativa, el mundo cambiaría instantáneamente. Pongámoslo así: pasaríamos a vivir en un mundo de Walt Disney: ¡todos los problemas tendrían solución!

No habría más enfermedades terminales ya que sabríamos cómo implementar curas para cada una y con drogas a medida, no habría más víctimas de inundaciones, ni de tornados o sequías, porque sabríamos con muchísima antelación cuándo y dónde se producirían las catástrofes naturales y por lo tanto podríamos evacuar las zonas potencialmente afectadas. Por otro lado, y siguiendo con esta lista de ejemplos, no faltaría comida para nadie y cada uno cubriría sus necesidades básicas (y más) con la dieta precisa para cada individuo todo el mundo tendría conocimiento sobre todos los temas que fueran de su interés en forma virtualmente instantánea... y así podría seguir con las fantasías más salvajes que se le ocurran. Pero no se ría, ni crea que estoy hablando de ciencia ficción: no. Claramente, el mundo sería otro.

Antes de que lo sugiera usted, me apuro a agregar el otro lado, el lado oscuro de todo este progreso: se terminaría la privacidad, no habría nada que no pudiéramos saber/averiguar, no habría más códigos de seguridad (porque todos se podrían crackear o romper), y a tal punto llegaría todo que toda persona que pueda disfrutar de la belleza de un cuadro, por ejemplo, podría pasar a pintarlo él o ella usando una computadora... en fin, creo que más o menos tiene una idea de lo que estoy hablando: ¡todo quedaría dado vuelta como una media!

Dicho todo esto, usted tiene todo el derecho del mundo a preguntarse si enloquecí. La respuesta puede que sea que sí, pero no por esto que estoy escribiendo. Lo que escribí más arriba es solo una brevísima porción de lo que podría pasar dependiendo de la respuesta que pudiéramos darle a una pregunta que martiriza al mundo de la matemática computacional: ¿es P = NP?

Sí, ya sé, ¿qué? Bien, lo que empecé escribiendo en el artículo tenía que ver con un desafío: ¿cómo hago para explicar de qué se trata el problema? ¿Qué quiere decir P? ¿Qué quiere decir NP? Y aun así, suponiendo que fuera capaz de explicarlo, ¿qué querrá decir que sean iguales o no? ¿Cómo podría afectar de forma semejante la vida del mundo? De eso se trata esta nota.

Voy a tener que hacer muchas simplificaciones y le pido que me las conceda como una licencia que combina su generosidad con mis propias limitaciones. Estuve muchísimo tiempo leyendo el material escrito sobre este tema y ahora quiero encontrar una forma de resumirlo. Voy a empezar así: la pregunta sobre si P es igual (o no) a NP tiene que ver con entender cuáles son los límites de lo que uno puede hacer con una computadora. Es decir, ya no hablemos de cuán rápidas van a ser o cuánta memoria se puede almacenar. No. Se trata de otra cosa: se trata de determinar de una vez y para siempre qué tipo de problemas se pueden o se podrán resolver a través del uso de las computadoras... y cuáles no.

Acompáñeme a recorrer estos ejemplos. Todos son casos particulares de lo que se llama la categoría de problemas NP.

Ejemplo 1: Suponga que yo le doy un rompecabezas que tiene un millón de piezas. Está claro que armarlo representaría un tema delicado. Pero usted advierte que si yo le trajera el rompecabezas armado, sería muy fácil determinar si la solución que yo le traigo es la correcta o no.

Ejemplo 2: Elija usted una clave o un password digamos de 10 caracteres, entre los cuales puede haber no solo números, sino también letras (mayúsculas, minúsculas) y símbolos (#,&,>, ~, ^, etc). Si yo quisiera romper ese código, es posible que tenga que dedicarle mucho tiempo y aun así, no está claro que pueda lograrlo. De hecho, usted basa la confianza que tiene en sus operaciones de Internet en que nadie podrá vulnerarlo, más allá de cuán cierto sea este hecho. Sin embargo, si usted me diera ese código, yo podría descubrir si es el correcto instantáneamente (bastaría con que pruebe una vez y ver si funciona).

Ejemplo 3: Tome todas las personas que tienen una cuenta en Facebook. Cada una de ellas tiene un grupo de amigos. Algunos de esos amigos tiene, a su vez, otros amigos además de usted. Pero bien podría pasar que hubiera algún subgrupo de amigos en donde todos son amigos entre todos en sus cuentas de Facebook. Suponga que usted se junta con 29 amigos a cenar los sábados por la noche. Junto a usted forman un grupo de 30 personas que voy a llamar “grupo de los sábados”. Supongamos también que todos tienen una cuenta en Facebook. Es esperable que todos sean amigos de todos. Es decir, si yo tomara cualquier par de integrantes del “grupo de los sábados” y me fijara en sus cuentas, ambos se tendrían como amigos. ¿Habrá algún equivalente a este “grupo de los sábados” pero que en lugar de tener 30 componentes tenga por lo menos 100? ¿Y habrá alguno que tenga por lo menos 1000?

Como en los ejemplos anteriores, encontrar estos conjuntos con estas características puede ser una tarea virtualmente imposible, pero si alguien viniera y le dijera que encontró uno, sería muy fácil verificar si es lo que buscábamos, ¿no?

Ejemplo 4 (éste es el que da origen al premio de un millón de dólares a quien lo resuelva): Suponga que usted tiene una lista de 400 estudiantes universitarios y necesita ubicarlos en dormitorios para dos personas. Uno de los problemas es que no hay lugar para todos sino que usted solamente podrá ubicar a 100 de ellos. Pero para complicar más las cosas, el rector de la universidad le adjunta una lista de pares de estudiantes que son incompatibles, en el sentido de que si usted llegara a elegirlos, no pueden estar juntos. Ahora, con estos datos, arme la lista.

Una advertencia antes de que empiece: el número de formas de seleccionar 100 estudiantes entre los 400 que le dio el rector es más grande que la cantidad de átomos que hay en el universo. Una vez más, ser capaz de escribir una lista con esas características puede ser inalcanzable, pero si yo le trajera la lista ya confeccionada, verificar si cumple o no con las restricciones es algo que podríamos hacer fácilmente.

Creo que con estos ejemplos alcanza. No abandone ahora ya que quiero compartir con usted en qué consiste el problema original. ¿Qué quiere decir que P sea igual (o no) a NP?

Hay (entre otros) dos tipos de problemas para las computadoras: unos reciben el nombre de “problemas de clase P” (la letra P proviene de la palabra polinomial). Estos son problemas considerados fáciles. Es decir, se pueden resolver en un tiempo razonable, que tiene relación con la complejidad del problema, pero se puede escribir un algoritmo que encuentre una solución sin que uno necesite esperar cien mil años. Por ejemplo, ordenar alfabéticamente cien millones de personas es una tarea que una computadora puede hacer sin mayores dificultades. Es un problema de clase P.

Hay otra clase de problemas que se llaman NP, en donde lo que es fácil (para una computadora) es verificar que una potencial respuesta es o no una buena solución, como vimos en los ejemplos que escribí más arriba. Puede que lleve muchísimo tiempo encontrar la tal solución, pero eso sí: si uno cree que encontró una, ¡listo! A partir de allí es muy fácil determinar si es o no correcta. Como en un rompecabezas gigante, encontrar la solución puede ser dificilísimo o virtualmente imposible, pero si alguien dice que tiene una, la exhibe y es muy fácil determinar si lo que dice es cierto o no.

En algún sentido las dos categorías son las siguientes: la categoría P está compuesta por los problemas para los cuales existe un algoritmo (un programa) con el cual una computadora en un tiempo “razonable” lo puede resolver.

La categoría NP consiste de los problemas en donde una computadora puede decidir en tiempo “razonable” si una solución es la correcta o no.

La pregunta entonces que involucra a P y a NP es la siguiente: ¿será verdad que esas dos categorías son iguales? ¿Será verdad que P = NP? Es decir, ¿será verdad que si uno tiene un problema en donde es fácil decidir –para una computadora– que una solución es correcta o no, es porque a ese problema en sí mismo es también fácil encontrarle una solución?

Y acá es donde uno necesita detenerse un instante: parece raro lo que estoy escribiendo, pero acompáñeme otra vez con el ejemplo del rompecabezas. Creo que se entiende bien que si uno cree que tiene una solución, decidir si lo es o no parece trivial, pero ¿cómo comparar esto con encontrar la solución? Aquí es donde yo agrego (pidiéndole la licencia para que me acepte lo que sigue): ¿y si cada pieza de un rompecabezas, por más gigante que sea, tuviera un número en la parte de atrás que va indicando qué piezas se engarzan con las de los números contiguos? ¿Y si hay algo que estos problemas tienen que nosotros todavía no sabemos? Si P fuera igual a NP, eso querría decir que todos los problemas de esta última clase tienen escondido una suerte de “atajo” que les permitiría a las computadoras llegar por el camino más corto a encontrar la solución perfecta.

Esta fue una introducción, una versión hipersimplificada y no escrita para matemáticos ni computadores, sino para que todos entendamos un poco más de qué se trata: el mundo de la computación está embarcado en decidir si estas dos categorías son iguales o no. La abrumadora mayoría de los especialistas en el tema sospecha que no, que no son iguales y que, por lo tanto, la fantasía de que el mundo se transforme en un gigantesco e imaginario parque de diversiones “a la Walt Disney” quedará en eso, en una fantasía... pero, hasta acá ¡nadie lo pudo probar! Es decir, nadie pudo probar hasta ahora que esas dos categorías son distintas... ni iguales.

Si lo hiciera, recibiría no sólo fama, prestigio y se transformaría en una de las celebridades más importantes de este siglo (y de la historia de la humanidad toda), sino que recibiría también un millón de dólares porque habría resuelto uno de los seis problemas (de los siete originales) que el Instituto Clay eligió en el año 2000 como los más importantes dentro del mundo de la matemática. Aunque también es posible que si la respuesta a la pregunta sobre si P = NP fuera afirmativa, entonces la misma persona podría encontrar formas de resolver los otros cinco problemas que aún quedan abiertos y en lugar de llevarse un millón, se llevaría seis...