DLOGTIME
Sign in to saveIn computational complexity theory, DLOGTIME is the complexity class of all computational problems solvable in a logarithmic amount of computation time on a deterministic Turing machine. It must be defined on a random-access Turing machine, since otherwise the input tape is longer than the range of cells that can be accessed by the machine. It is a very weak model of time complexity: no random-access Turing machine with a smaller deterministic time bound can access the whole input.
Article · Português
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.
Abstract from DBpedia / Wikipedia · CC BY-SA