DLOGTIME

Questa voce o sezione sugli argomenti matematica e teorie dell'informatica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

Questa voce sugli argomenti matematica e teorie dell'informatica è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Teknopedia. Segui i suggerimenti del progetto di riferimento.

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.^{[senza fonte]} 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.^[1]

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.

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica