Función de espacio constructivo
- Función de espacio constructivo
-
En teoría de la complejidad computacional, se dice que una funció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, 2n y n!. Si S1(n) y S2(n) son funciones de espacio constructivo, también lo son S1(n)S2(n), 2S1(n) y S1(n)S2(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.
Wikimedia foundation.
2010.
Mira otros diccionarios:
Función de espacio constructivo — En teoría de la complejidad computacional, se dice que una función S de los naturales en los naturales 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… … Enciclopedia Universal
Espacio — Saltar a navegación, búsqueda Espacio (del latín spatium) se refiere: Especialmente al espacio físico, en el que se ubican los objetos sensibles; y la extensión que contiene toda la materia existente; la distancia entre dos cuerpos; la distancia… … Wikipedia Español
Jerarquía de clases de complejidad acotadas por 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 … Wikipedia Español
Tracción delantera — Motor delantero transversal / tracción delantera. La tracción delantera, denominado en inglés como «FWD» de Front Wheel Drive, es un sistema en el que el par del motor se transmite sólo a las ruedas delanteras. Es el mismo eje en el que se… … Wikipedia Español
Historia del arte — Para la historiografía de la historia del arte, véase Estudio de la historia del arte. La creación … Wikipedia Español
Arquitectura bizantina — Saltar a navegación, búsqueda … Wikipedia Español
Edad Media — Santa Sofía de Constantinopla (532 537). Los cuatro minaretes son una adición correspondiente a su transformación en mezquita, a raíz de la … Wikipedia Español
Biorreactor — Saltar a navegación, búsqueda Biorreactor a escala de laboratorio conteniendo células animales. Un biorreactor es un recipiente o sistema que mantiene un ambiente biológicamente activo. En algunos casos, un biorreactor es un recipiente en el que… … Wikipedia Español
Energías renovables en la escala doméstica — Saltar a navegación, búsqueda Contenido 1 Energías Alternativas en la escala doméstica 2 La cuestión energética en la Argentina 3 Matriz energética … Wikipedia Español
Anexo:Glosario de arquitectura — Para un glosario limitado al período prehistórico, véase Anexo:Glosario de arquitectura prehistórica. Índice: A B C D E F G H I J K L M N Ñ O P Q R S T U V W X Y Z … Wikipedia Español
