Função construível

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Este artigo não cita fontes confiáveis e independentes. (desde abril de 2014). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

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[editar | editar código-fonte]

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 n0 e uma máquina de Turing M tais que, dada uma cadeia 1n consistindo de n uns, M pára após exatamente f(n) passos para todo nn0. 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 1n, 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 1n 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[editar | editar código-fonte]

Similarmente, uma função f é espaço-construível se existe um inteiro positivo n0 e uma máquina de Turing M tal que, dada uma cadeia 1n consistindo de n uns, M pára após usar exatamente f(n) células para todo nn0. De maneira equivalente, uma função f é espaço-construível se existe uma máquina de Turing M tal que, dada uma cadeia 1n 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 1n consistindo de n uns, M pára após usar exatamente f(n) células.

Exemplos[editar | editar código-fonte]

Todas as funções f(n) (tais como n, nk, 2n) 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[editar | editar código-fonte]

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.