Problemas P Y Np

PROBLEMAS P Y NP

Los recursos comúnmente estudiados en complejidad computacional son:
– El tiempo: mediante una aproximación al número de pasos de ejecución que un algoritmo emplea para resolverun problema.
– El espacio: mediante una aproximación a la cantidad de memoria utilizada para resolver el problema.

Los problemas se clasifican en conjuntos o clases de complejidad (L, NL, P,PCompleto, NP, NP-Completo, NP Duro...).Nosotros nos vamos a centrar en las clases P y NP.

Consideremos, por ejemplo, el Problema de la suma de subconjuntos, que es un ejemplo de un problema fácil deverificar, pero cuya respuesta se cree (pero no ha sido demostrado) es difícil de calcular/hallar. Dado un conjunto de números enteros, ¿existe un subconjunto no vacío de ellos donde la suma de suselementos es igual a 0? por ejemplo, ¿existe un subconjunto del conjunto {−2, −3, 15, 14, 7, −10} tal que la suma de sus elementos sea 0? La respuesta es SI, si bien puede llevar algún tiempo encontrarun subconjunto que satisface el requerimiento, según cual sea el tamaño del conjunto y subconjunto. Por otra parte, si alguien afirma que la respuesta es: «sí, porque la suma de {−2, −3, −10, 15} esigual a cero», entonces lo podemos comprobar en forma muy rápida y mediante unas pocas cuentas. Verificar que la suma del subconjunto es cero es un proceso mucho más rápido que encontrar el subconjunto.La información necesaria para verificar un resultado positivo/afirmativo es llamada un certificado. Por lo que podemos concluir que dado los certificados apropiados, es posible verificar rápidamentelas respuestas afirmativas de nuestro problema (en tiempo polinomial) y es ésta la razón por la que el problema se encuentra en NP. Una respuesta a la pregunta P = NP sería determinar si en problemasdel tipo SUMA-SUBCONJUNTO es tan fácil hallar la solución como verificarla. Si se encuentra que P no es igual a NP, ello significa que algunos problemas NP serían significativamente más difíciles de...