|
El problema P contra NP El matemático Stephen Cook, que formuló este problema en 1971, lo explica con el siguiente ejemplo: | Es sábado por la noche y llega usted a una fiesta abarrotada de gente. La anfitriona le dice: "Creo que conoces a Rosa, aquella chica de la esquina que lleva un vestido rojo". A usted le bastará una fracción de segundo para verificar si la anfitriona está en lo cierto o no. Pero si en vez de eso la anfitriona le hubiera dicho "Mira por ahí a ver si conoces a alguien", usted puede tardar tres horas en hallar la respuesta. |
Por increible que parezca, esta cuestión supone un problema enorme para los lógicos y para los científicos de la computación. Las siglas P y NP se refieren a los tiempos "polinómico" y "polinómico no determinista".
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. Otro ejemplo: Comprobar 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, Problema P (dificil de encontrar) contra NP (fácil de verificar)? 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, resolución de ecuaciones, la realización de sumas, productos, 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),... 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. 
Está claro que todo problema P es también NP, esto es, todo problema resoluble en tiempo polinomial mediante un algoritmo adecuado (P), es también un problema que admite una comprobación rápida (NP). Pero, ¿y al revés?. ¿Existen problemas NP que no sean P?. Esto es, ¿existen problemas que admiten una comprobación de solución o no solución conjeturada y, en cambio, no admiten en tiempo polinomial una resolución algoritmica? En el cálculo computacional pueden presentarse problemas en donde el número de alternativas posibles para una determinada condición de proceso es tan grande que ni siquiera con las supercomputadores existentes aún en nuestra tecnología se podrían afrontar en toda la vida de un ser humano, pues no tendría para ello el suficiente tiempo (es el problema P). En cambio, la verificación de que una determinada alternativa verifica la condición de proceso es algo prácticamente instantáneo (es el problema NP). Ejemplo: Queremos colocar 6000 libros en 200 estantes, de modo que se cumpla la condición de que no estén juntos ciertos libros de diferente materia, nos encontramos que el número de alternativas posibles podría superar al número de átomos de la Vía Láctea, con lo cual, el determinarlas todas (problema P - difícil de encontrar) es precisamente eso, muy difícil en la actual tecnología de la computación. En cambio, el verificar una de estas alternativas como válida, cuando alguien conjetura una solución, (problema NP - fácil de verificar) es inmediato. |
En estos ejemplos, en los que el problema NP es comprobable de inmediato, pero el problema P parece no existir, ¿se debe esto a que realmente el problema P no es posible o bien que no se tiene la tecnología computacional adecuada para su resolución de forma algoritmica en tiempo polinomial? Esta es la pregunta no contestada que da consistencia al problema. Entre los ejemplos actuales más candentes está el de la criptografía y la comprobación de claves informaticas (NP) en contraposición al problema de generación algoritmica de tales claves en un tiempo polinomial (P). ¿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. Nota de cine: Cada vez que Charlie Epps (Serie de TV Numb3rs) se encuentra bajo de ánimo o deprimido, va a su garaje a trabajar sobre el problema P vs NP |
ArtÃculos 
