¿Que es 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 2O(n)

, y es por lo tanto igual a la clase de

complejidad DTIME(2O(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(2p(n)

), dondep(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