DLOGTIME
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.
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 | editar código]- Michael Sipser (2006). «Sections 8.14&ndash». Introdução à Teoria da Computação. [S.l.]: THOMSON. pp. 324–325. ISBN 0-534-95097-3