Share to:

 

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.

Bibliografia

Ligação externa

Information related to DLOGTIME

Prefix: a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9

Portal di Ensiklopedia Dunia

Kembali kehalaman sebelumnya