Complejidad en espacio

En teoría de la complejidad computacional se utilizan diferentes clases de complejidad para catalogar familias de problemas de decisión en relación con la cantidad de espacio que utilizan para ser resueltos. Estas clases de complejidad pueden ser organizadas en una "jerarquía de clases de complejidad acotadas por espacio".
Sea una función S: \mathbb{N}\rightarrow\mathbb{N}....