Função construível

Na teoria da complexidade, uma função tempo-construível é uma função f dos números naturais para números naturais com a propriedade de que f(n) pode ser construída a partir de n por uma máquina de Turing em tempo de ordem f(n). A finalidade de tal definição é excluir funções que não provêm um limitante superior sobre o tempo de execução de alguma máquina de Turing.

Definições tempo-construíveis

Existem duas definições diferentes para funções tempo-construíveis. Na primeira definição, uma função f é chamada tempo-construível se existe um inteiro positivo n₀ e uma máquina de Turing M tais que, dada uma cadeia 1ⁿ consistindo de n uns, M pára após exatamente f(n) passos para todo n ≥ n₀. Na segunda definição, uma função f é chamada tempo-construível se existe uma máquina de Turing M tal que, dada uma cadeia 1ⁿ, M gera como saída a representação binária de f(n) em tempo O(f(n)) (uma representação binária pode ser utilizada ao invés desta, uma vez que os dois podem ser interconvertidos em tempo O(f(n))).

Existe também uma noção de função totalmente tempo-construível. Uma função f é chamada totalmente tempo-construível se existe uma máquina de Turing M tal que, dada uma cadeia 1ⁿ consistindo de n uns, M pára após exatamente f(n) passos. Esta definição é um pouco menos geral do que as duas primeiras, mas, para a maioria das aplicações, qualquer definição pode ser usada.

Definições espaço-construíveis

Similarmente, uma função f é espaço-construível se existe um inteiro positivo n₀ e uma máquina de Turing M tal que, dada uma cadeia 1ⁿ consistindo de n uns, M pára após usar exatamente f(n) células para todo n ≥ n₀. De maneira equivalente, uma função f é espaço-construível se existe uma máquina de Turing M tal que, dada uma cadeia 1ⁿ consistindo de n uns, M gera como saída a representação binária (ou unária) de f(n), enquanto usa somente espaço O(f(n)).

Igualmente, uma função f é totalmente espaço-construível se existe uma máquina de Turing M tal que, dada uma cadeia 1ⁿ consistindo de n uns, M pára após usar exatamente f(n) células.

Exemplos

Todas as funções f(n) (tais como n, n^k, 2ⁿ) que são comumente usadas são tempo- e espaço-construíveis, enquanto f(n) for, pelo menos, cn, para uma constante c > 0. Nenhuma função que seja o(n) pode ser tempo-construível, a menos que seja, eventualmente, constante, visto que não há tempo suficiente para ler toda a entrada. No entanto, log(n) é uma função espaço-construível.

Aplicações

Funções tempo-construíveis são usadas em resultados da teoria da complexidade, tais como o teorema de hierarquia de tempo. Elas são importantes porque o teorema de hierarquia de tempo depende de máquinas de Turing que precisam executar em tempo O(f(n)) quando um algoritmo leva mais do que f(n) passos. Obviamente, isto é impossível sem que se seja capaz de calcular f(n) neste tempo. Tais resultados são tipicamente verdadeiros para todas as funções naturais f, mas não são necessariamente verdadeiras para f construída artificialmente. Para formulá-las precisamente, é necessário ter uma definição precisa para uma função natural f para a qual o teorema é verdadeiro. Funções tempo-construíveis são frequentemente usadas para fornecer tal definição.

Funções espaço-construíveis são usadas de maneira similar, por exemplo, no teorema de hierarquia de espaço.