COMPLEJIDAD COMPUTACIONAL
La Teoría de la complejidad computacional es la parte de la teoría de la computación que estudia los recursos requeridos durante el cálculo para resolver un problema. Los recursos comúnmente estudiados son el tiempo (número de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (cantidad de memoria utilizada para resolver un problema).
Se pueden estudiar igualmente otros parámetros, tales como el número de procesadores necesarios para resolver el problema en paralelo. La teoría de la complejidad difiere de la teoría de la computabilidad en que esta última se ocupa de la factibilidad de expresar problemas como algoritmos efectivos sin tomar en cuenta los recursos necesarios para ello.
Costo inherente de la solución de un problema en la computación científica a gran escala, medido por el número de operaciones requeridas así como también por la cantidad de memoria usada y el orden en que se usa.
El resultado de un análisis de complejidad es una estimación de cuán rápidamente aumenta el tiempo de la solución a medida que aumenta el tamaño del problema, la que puede utilizarse para analizar problemas y ayudar en el diseño de algoritmos para su solución.
El resultado de un análisis de complejidad es una estimación de cuán rápidamente aumenta el tiempo de la solución a medida que aumenta el tamaño del problema, la que puede utilizarse para analizar problemas y ayudar en el diseño de algoritmos para su solución.
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)), 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/
