DLOGTIME
# DLOGTIME

Nella teoria della complessità computazionale DLOGTIME è la classe di complessità di tutti i problemi computazionali risolvibili in una quantità logaritmica di tempo computazionale da una macchina di Turing deterministica. Essa è la più piccola classe non banale che usa le risorse del tempo deterministico. Deve essere definita su una macchina di Turing ad accesso casuale, poiché altrimenti la macchina non ha il tempo di leggere l'intero input a nastro.

L'uniformità DLOGTIME è importante nella complessità dei circuiti.

Il problema di verificare la lunghezza della stringa di input può essere risolto in DLOGTIME, mediante la ricerca binaria delle possibili dimensioni dell'input.

