DLOGTIME
Questa voce o sezione sugli argomenti matematica e teorie dell'informatica non cita le fonti necessarie o quelle presenti sono insufficienti.
Questa voce sugli argomenti matematica e teorie dell'informatica è solo un abbozzo.
Contribuisci a migliorarla secondo le convenzioni di Wikipedia. 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.
Note
- ^ (EN) Bozzano G Luisa, Algorithms and Complexity.
V · D · M | |
---|---|
P · NP · co-NP · NP-C · co-NP-C · NP-hard · UP · #P · #P-C · L · NL · NC · P-C · PSPACE · PSPACE-C · EXPTIME · EXPSPACE · PR · RE · Co-RE · RE-C · Co-RE-C · R · BQP · BPP · RP · ZPP · PCP · IP · PH |
Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica