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.
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
[modifica | modifica wikitesto]- ^ (EN) Bozzano G Luisa, Algorithms and Complexity.