Funció d'espai constructiu

En teoria de la complexitat computacional, es diu que una funció $S:\mathbb{N}\to \mathbb{N}$ és una funció d'espai constructiu si existix una Màquina de Turing que tota entrada de llongitut n utilisa com a molt S(n) caselles (sense contar les caselles de l'entrada) i ademés, per a tot natural n existix una entrada de llongitut n que utilisa exactament S(n) caselles.

Les funcions d'espai constructiu s'utilisen per a definir classes de complexitat acotades per espai.

Entre les funcions d'espai constructiu estan les funcions log(n), n, 2ⁿ i n!. Si S₁(n) i S₂(n) són funcions d'espai constructiu, també ho són S₁(n)S₂(n), 2^S₁(n) i S₁(n)^S₂(n).

Si adicionalment, existix una Màquina de Turing tal que tota entrada de llongitut n utilisa exactament S(n) caselles, es diu que la funció S és d'espai completament constructiu. Totes les funcions d'espai constructiu acotades inferiormente per la funció n són d'espai completament constructiu.

Bibliografia

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