Complejidad Computacional

Clases de Complejidad

Los problemas de decisión se clasifican en conjuntos de complejidad comparable llamados clases de complejidad.

La clase de complejidad P es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina determinista en tiempo polinómico, lo que corresponde intuitivamente a problemas que pueden ser resueltos aún en el peor de sus casos.

La clase de complejidad NP es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina no determinista en tiempo polinómico. Esta clase contiene muchos problemas que se desean resolver en la práctica, incluyendo el problema de satisfactibilidad booleana y el problema del viajante, un camino Hamiltoniano para recorrer todos los vértices una sola vez. Todos los problemas de esta clase tienen la propiedad de que su solución puede ser verificada efectivamente.


La pregunta P=NP

Preguntas como esta motivan la introducción de los conceptos de hard (difícil) y completo. Un conjunto X de problemas es hard con respecto a un conjunto de problemas Y ( 'Y' pertenecientes a NP) si X>Y o X=Y, es decir Y se puede escribir como un conjunto de soluciones de los problemas X. En palabras simples, Y es "más sencillo" que X. El término sencillo se define precisamente en cada caso. El conjunto hard más importante es NP-hard. El conjunto X es completo para Y si es hard para Y y es también un subconjunto de Y (caso X=Y). El conjunto completo más importante es NP-completo. En otras palabras, los problemas del conjunto NP-completo tienen la característica de que, si se llega a encontrar una solución en tiempo P para algún miembro del conjunto (cualquiera de los problemas de NP-completo), entonces de hecho existe una solución en tiempo P para todos los problemas de NP-completo.

Intratabilidad
Los problemas que pueden ser resueltos en teoría, pero no en práctica, se llaman intratables. Qué se puede y qué no en la práctica es un tema debatible, pero en general sólo los problemas que tienen soluciones de tiempos polinomiales son solubles para más que unos cuantos valores. Entre los problemas intratables se incluyen los de EXPTIME-completo. Si NP no es igual a P, entonces todos los problemas de NP-completo son también intratables.

Para ver por qué las soluciones de tiempo exponencial no son útiles en la práctica, se puede considerar un problema que requiera 2n operaciones para su resolución (n es el tamaño de la fuente de información). Para una fuente de información relativamente pequeña, n=100, y asumiendo que una computadora puede llevar a cabo 1010 (10 giga) operaciones por segundo, una solución llevaría cerca de 4*1012 años para completarse, mucho más tiempo que la actual edad del universo.





decsai.ugr.es/~smc/docencia/mittr2.pdf
http://es.wikipedia.org/wiki/Clases_de_complejidad_P_y_NP
www.dm.uba.ar/materias/optimizacion/2006/1/fbonomo_clase_npc.pdf
http://es.wikipedia.org/wiki/Complejidad_computacional