Algunas clases

PSPACE
En teoría de la complejidad computacional, la clase PSPACE es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio polinomial  y tiempo ilimitado.
NPSPACE
En teoría de la complejidad computacional, la clase de complejidad NPSPACE es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no-determinista en espacio polinómico y tiempo ilimitado.
P
En teoría de la complejidad, la clase de complejidad de los problemas de decisión que pueden ser resueltos en tiempo polinómico calculado a partir de la entrada por una máquina de Turing determinista es llamada P.


EXPTIME
En teoría de la complejidad computacional, la clase de complejidad EXPTIME (también llamada EXP) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(2^p(n)), donde p(n) es una función polinomial sobre n.

Np
En teoría de la complejidad computacional, NP ("tiempo polinomial no determinista"). Es el conjunto de problemas que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinista.
NL
En teoría de la complejidad computacional, la clase de complejidad NL (espacio logarítmico no determinista) 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 no determinista tal que la solución si existe es única. La clase L está contenida en NL y está contenida estrictamente en PSPACE. 
SL
La clase de complejidad SL (espacio logarítmico simétrico, del inglés Symmetric Logspace o Sym-L) es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing no determinista en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada.
EXPSPACE
La clase de complejidad 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. (Cuando se restringe p(n) como una función lineal, la clase resultante se denomina ESPACE.)

 L
La clase de complejidad L (LSPACE o espacio logarítmico determinista) 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. La clase L está contenida en NL y está contenida estrictamente en PSPACE. 

Entre muchas clases mas.

referncias:
http://es.wikipedia.org/wiki/Anexo:Clases_de_complejidad