p vs np

La relación entre las clases de complejidad P y NP es una pregunta que aún no se ha podido responder por la teoría de la complejidad computacional. En esencia, la pregunta ¿es P = NP ? significa: si es posible "verificar" rápidamente soluciones positivas a un problema del tipo SI/NO (donde "rápidamente" significa "en tiempo polinómico"), ¿es que entonces también se pueden "obtener" las respuestasrápidamente?
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 resolver un 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.
Se lo considera el problema más importante en este campo--el Clay Mathematics Institute ha ofrecido un premio de un millón de dólares estadounidenses para quién desarrolle la primera demostración correcta.
Índice [ocultar]
1 Ejemplo
2 Contexto del problema
3 Definiciones formales
4 La clase P
5 La clase NP
6NP-Completo
7 Véase también
8 Referencias
9 Bibliografía
10 Enlaces externos
Ejemplo[editar]

Consideremos, por ejemplo, el Problema de la suma de subconjuntos, que es un ejemplo de un problema fácil de verificar, 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 sumade sus elementos 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 encontrar un 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} es igual 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 verificarrápidamente las 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 problemas del 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ásdifíciles de hallar su solución que verificar la misma. La respuesta sería aplicable a todo este tipo de problemas, no solo al ejemplo específico de SUMA-SUBCONJUNTO.
La restricción a problemas de tipo SI/NO realmente no es importante; aún si se permiten respuestas más complicadas, el problema resultante resulta equivalente (o sea si FP = FNP).
Contexto del problema[editar]

La relación entre lasclases de complejidad P y NP es estudiada por la teoría de la complejidad computacional, la parte de la teoría de la computación que trata de los recursos requeridos durante el cálculo para resolver un problema dado. Los recursos más usuales son tiempo (¿cuántos pasos son necesarios para resolver un problema?) y espacio (¿cuánta memoria es necesaria para resolver un problema?).
En este tipo deanálisis, se requiere un modelo de la computadora para la que desea estudiar el requerimiento en términos de tiempo. Típicamente, dichos modelos suponen que la computadora es determinista (dado el estado actual de la computadora y las variables de entrada, existe una única acción posible que la computadora puede tomar) y secuencial (realiza las acciones una después de la otra). Estas suposiciones...