Complejidad Computacional

Vamos a analizar lo que es la complejidad computacional. Una de las cosas más importantes a tomar en cuenta al momento de seleccionar un algoritmo es el tiempo que se va a tardar en arrojar una salida. En ves de calcular el tiempo exacto que se puede tardar nuestro algoritmo, se calcula la cantidad de operaciones en función del tamaño de la entrada (n). Para estimar el tiempo de ejecución, esta función de crecimiento se multiplica por una constante c que representa una estimación del tiempo que una computadora se tarda en realizar una operación.

Los problemas de decisión son los problemas en donde las dos respuestas posibles sin “si” y “no”. También se puede definir como el problema de decidir si una cierta frase pertenece a un conjunto dado de frases, o lenguaje formal. El conjunto contiene exactamente las frases para las cuales la respuesta a la pregunta es positiva. Si existe un algoritmo que pueda decidir para cada posible frase de entrada si esa frase pertenece al lenguaje, entonces se dice que el problema es decidible, de otra forma se dice que es un problema indecidible.

Los problemas de decisión se pueden clasificar en clases de complejidad, las cuales son:

• La clase de complejidad P, la cual está formada por todos aquellos problemas de decisión para los cuales se tiene un algoritmo de solución que se ejecuta en tiempo polinomial en una máquina determinista.
• La clase de problemas NP la cual está formada por todos aquellos problemas de decisión para los cuales existe un algoritmo de solución que se ejecuta en tiempo polinomial en una máquina no determinista. Dicho de otro modo, no se ha encontrado un algoritmo determinista que lo resuelva en tiempo polinomial.

La relación entre la clase P y la clase NP es estrecha: . Cualquier problema de decisión resuelto por un algoritmo determinístico en tiempo polinomial también es resuelto por un  algoritmo no determinístico en tiempo polinomial.

*Este diagrama muestra la teoría de que todos los problemas P y NP-Completo son problemas NP, aunque no ha sido probada es la mas aceptada como probable.

 

 

Algunas clases

• TIME: o DTIME, es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(f(n)), y espacio ilimitado.
• E: es el conjunto de problemas de decisión que pueden ser resueltos por una Máquina de Turing determinista en tiempo 2^O(n), y es por lo tanto igual a la clase de complejidad DTIME(2^O(n)).
• NC: es el conjunto de los problemas de decisión que pueden ser resueltos mediante computación paralela con un número polinómico de procesadores en tiempo polilogarítmico.
• NTIME: la clase de complejidad NTIME(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no-determinista en tiempo O(f(n)) y espacio ilimitado.
• PP: es una clase de problema de decisión, resoluble por una máquina de Turing probabilística, diferente de la máquina de Turing general o determinística en que las transiciones entre estados tienen la misma probabilidad de ocurrencia.
• DSPACE: es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en espacio O(f(n)) y tiempo ilimitado. Es la contrapartida determinista de la clase NSPACE.
• EXPSPACE:es el conjunto de los problemas de decisión que pueden ser resueltos con una máquina de Turing determinista en espacio O(2^p(n)), donde p(n) es una función polinomial sobre n.
• L: es el conjunto de los problemas de decisión que pueden ser resueltos en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada, por una máquina de Turing determinista tal que la solución si existe es única.
• NSPACE: es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no-determinista en espacio O(f(n)) y tiempo ilimitado. NSPACE es la contrapartida no-determinista de DSPACE.

 

Esta es la página de la organización que da 1 millón de dólares a quien resuelva el problema de P vs NP: http://www.claymath.org/millennium/P_vs_NP/

Referencias:

• http://www.di.uniovi.es/~dani/asignaturas/transparencias-leccion19.PDF
• http://es.wikipedia.org/wiki/EXPTIME