DLOGTIME
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Julho de 2011) |
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.
Bibliografia
editar- Michael Sipser (2006). «Sections 8.14&ndash». Introdução à Teoria da Computação. [S.l.]: THOMSON. pp. 324–325. ISBN 0-534-95097-3