La cuestión de la inclusión estricta entre las clases de complejidad P y NP es uno de los problemas abiertos más importantes de las matemáticas. El Instituto Clay de Matemáticas (Cambridge, Massachusetts) premia con un millón de dólares a quién sea capaz de lograr la resolución de esta conjetura. Alguien en una ocasión me explicó éste problema con un ejemplo muy sencillo de entender. Me apostaría lo que fuese a que la mayoría de los lectores de aquí no sabrían resolver manualmente una raíz cuadrada, aunque no me cabe ninguna duda a que todos sabrían elevar un determinado número al cuadrado. Llegamos a la conclusión que resolver una raíz cuadrada (que existe un método muy laborioso) es más complicado o lento que la operación inversa.
Si un problema nos pide que comprobemos si un número determinado X es la raíz cuadrada de Z podríamos resolverlo de dos formas:
- Calculando la raíz de Z y comparando con X (proceso lento y engorroso)
- O bien, elevando al cuadrado a X y comparando con Z (simple multiplicación X·X)
La conclusión que sacamos de éste sencillo ejemplo es que en algunos problemas comprobar la solución es más eficiente que calcularla. La complejidad de la función “elevar al cuadrado” es más simple que calcular la raíz cuadrada. ¿Qué tiene que ver todo esto con P=NP? Pues bien, P es la clase de complejidad que contiene problemas de decisión que se pueden resolver en un tiempo polinómico. P contiene a la mayoría de problemas naturales, algoritmos de programación lineal, funciones simples,... Por ejemplo la suma de dos números naturales se resuelven en tiempo polinómico (para ser más exactos es de orden 2n). Entre los problemas que se pueden resolver en tiempo polinómico nos encontramos con diversas variedades como los logarítmicos (log(n)), los lineales (n), los cuadráticos (n2), los cúbicos (n3),... Volviendo al ejemplo principal llegamos a la conclusión que la función de elevar al cuadrado está contenida en la clase P.
La clase de complejidad NP contiene problemas que no pueden resolverse en un tiempo polinómico. Cuando se dice que un algoritmo no puede obtener una solución a un problema en tiempo polinómico siempre se intenta buscar otro procedimiento que lo consiga mejorar. Frente a los problemas contenidos en P tienen métodos de resolución menos eficaces. Podemos ver que la operación de calcular la raíz cuadrada se encuentra contenida en esta clase.
Si nos resulta sencillo encontrar una solución para un determinado problema, sabemos comprobar si la solución es cierta (simplemente comparar), por lo que P es un subconjunto de la clase NP. La gran cuestión es si ocurre lo mismo a la inversa, es decir, si tengo un problema que sé comprobar fácilmente si un resultado es una solución, ¿sé calcular una solución sencillamente? ¿Todo problema se puede resolver en tiempo polinómico? Si alguien conoce la respuesta que se dirija al Instituto Clay y recoja su millón de dólares.
Más información | P versus NP en Wikipedia (Inglés)
Ver 8 comentarios