L (complessità)

Nella teoria della complessità computazionale, L è la classe di complessità che contiene i problemi di decisione che possono essere risolti da una macchina di Turing deterministica usando una quantità logaritmica di memoria. Intuitivamente, uno spazio logaritmico è sufficiente a contenere un numero costante di puntatori nell'input, e un numero logaritmico di valori booleani.
Per saperne di più visita Wikipedia.org...