Función de espacio constructivo

En teoría de la complejidad computacional, se dice que una función $S:\mathbb {N} \rightarrow \mathbb {N}$ es una función de espacio constructivo si existe una Máquina de Turing que toda entrada de longitud n utiliza a lo sumo S(n) casillas (sin contar las casillas de la entrada) y además, para todo natural n existe una entrada de longitud n que utiliza exactamente S(n) casillas.

Las funciones de espacio constructivo se utilizan para definir clases de complejidad acotadas por espacio.

Entre las funciones de espacio constructivo están las funciones log(n), n, 2ⁿ y n!. Si S₁(n) y S₂(n) son funciones de espacio constructivo, también lo son S₁(n)S₂(n), 2^S₁(n) y S₁(n)^S₂(n).

Si adicionalmente, existe una Máquina de Turing tal que toda entrada de longitud n utiliza exactamente S(n) casillas, se dice que la función S es de espacio completamente constructivo. Todas las funciones de espacio constructivo acotadas inferiormente por la función n son de espacio completamente constructivo.

Bibliografía

• J. Hopcroft y J.D. Ullman. Introduction to Automata theory, Languages and Compilation. Addison Wesley. 1979. Capítulo 12 — Computational Complexity Theory.

• Datos: Q5870974