DLOGTIME

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Text document with red question mark.svg
Este artigo ou secção contém uma ou mais fontes no fim do texto, mas nenhuma é citada no corpo do artigo, o que compromete a confiabilidade das informações. (desde julho de 2011)
Por favor, melhore este artigo introduzindo notas de rodapé citando as fontes, inserindo-as no corpo do texto quando necessário.


DLOGTIME é a classe de complexidade de todos problemas computacionais solúveis em uma quantidade logarítimica de tempo computacionais por uma máquina de Turing determinística. É a menor classe não-trivial utilizando o recurso de tempo determinístico. Esta deve ser definida em uma máquina de Turing de acesso aleatório, visto que de outra forma não haveria tempo para ler toda a fita de entrada.

A uniformidade de DLOGTIME é importante na teoria de complexidade dos cicuitos.

O problema de testar o comprimento de uma entrada pode ser solucionado em DLOGTIME, utilizando busca binária para possíveis tamanhos.

Referências[editar | editar código-fonte]