El dilema de los problemas que nadie puede resolver (pero todos pueden verificar)

Si alguien te entrega un rompecabezas de diez mil piezas completamente mezcladas y te desafía a armarlo, te llevaría días, tal vez semanas de frustrante trabajo. Sin embargo, si esa misma persona te entrega el rompecabezas ya terminado, te bastaría un solo vistazo de un segundo para comprobar si es correcto o si falta alguna pieza.

Esta premisa, que parece una simple curiosidad cotidiana, esconde uno de los mayores misterios de la ciencia moderna. En el corazón de la matemática y la informática teórica existe una pregunta que vale un millón de dólares: ¿Existen problemas cuya solución es increíblemente difícil de encontrar, pero ridículamente fácil de verificar?

La delgada línea entre buscar y comprobar

En el ámbito científico, esta brecha se formaliza mediante dos conjuntos de problemas conocidos como P y NP.

-Los problemas P (Polinómicos): Son aquellos que las computadoras pueden resolver de manera eficiente en un tiempo razonable. Calcular la ruta más corta entre dos ciudades usando el GPS o clasificar una lista de nombres en orden alfabético entran en esta categoría.

-Los problemas NP (Tiempo Polinómico No Determinista): Son aquellos cuya solución es un misterio, pero que, si alguien nos da la respuesta correcta, podemos verificar que es real de forma ultrarrápida.

El enigma reside en si estos dos conjuntos son, en realidad, el mismo. Es el famoso problema matemático de P no es igual a NP, uno de los siete Problemas del Milenio. Si se demostrara que P = NP, significaría que cualquier problema cuya respuesta sea fácil de verificar también es fácil de resolver. Solo tendríamos que ser lo suficientemente listos como para encontrar el algoritmo adecuado.

El laberinto del tiempo impracticable

Para entender la magnitud de un problema "impracticable", viajemos al terreno de la criptografía, el escudo invisible que protege tus contraseñas, tus datos bancarios y tus compras en línea.

La seguridad de internet se basa en la asimetría del tiempo. Multiplicar dos números primos gigantescos (por ejemplo, de 200 dígitos cada uno) es una tarea que una computadora ordinaria realiza en un abrir y cerrar de ojos. El resultado es un número colosal.

Sin embargo, el proceso inverso —tomar ese número colosal y descubrir cuáles fueron los dos números primos originales que lo generaron (factorización de enteros)— es un desafío titánico. No existe un método directo. La única opción para una computadora actual es probar combinaciones mediante la fuerza bruta.

Si quisiéramos romper una de estas claves actuales por pura fuerza bruta, una supercomputadora tardaría más tiempo del que le queda de vida al universo entero antes de que el Sol se apague. Es un tiempo impracticable.

Y aquí está la magia: si yo te doy el número colosal y, además, te susurro al oído los dos números primos originales, solo tendrás que multiplicarlos en tu calculadora para verificar en un milisegundo que mi respuesta es matemáticamente perfecta.

Del repartidor de paquetes al plegamiento de proteínas

Este fenómeno no solo afecta a los espías y a los bancos; impacta de lleno en nuestra vida diaria y en el avance de la medicina.

Un ejemplo clásico es el Problema del Viajante (TSP, por sus siglas en inglés). Si un repartidor tiene que pasar por 5 ciudades, es fácil encontrar la ruta más corta. Si las ciudades aumentan a 50, las combinaciones posibles superan el número de átomos en el universo observable. Diseñar la ruta perfecta es impracticable; verificar si una ruta propuesta cumple con un límite de tiempo óptimo es inmediato.

En la biología molecular ocurre algo similar con el plegamiento de proteínas. Saber cómo se va a plegar una cadena de aminoácidos tridimensionalmente para diseñar un fármaco contra el cáncer puede requerir simulaciones computacionales eternas. Pero si la naturaleza (o una inteligencia artificial avanzada) nos propone una estructura, comprobar si los enlaces químicos son estables es un proceso sumamente rápido.

¿Y si resolviéramos el misterio?

La comunidad científica se inclina a pensar que, efectivamente, P no es igual a NP. Es decir, que el universo es inherentemente asimétrico y que buscar siempre será más difícil que comprobar.

Si un genio de la informática demostrara lo contrario (P = NP), el mundo cambiaría de la noche a la mañana. La criptografía actual se desmoronaría, pero a cambio, la optimización logística sería perfecta, la cura de enfermedades se automatizaría y la inteligencia artificial alcanzaría cotas inimaginables.

Mientras tanto, vivimos en un mundo protegido y limitado por esa hermosa brecha: la certeza de que verificar la verdad sigue siendo mucho más fácil que descubrirla.