French
DeutschL (complessità)
Nella teoria della complessità computazionale, L (nota anche come LSPACE, LOGSPACE o DLOGSPACE) è 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.
Una generalizzazione di L è NL, la classe dei linguaggi decidibili in spazio logaritmico da una macchina di Turing non deterministica. Banalmente si può dire che . Inoltre, un decisore che usa spazio non può impiegare un tempo superiore a , poiché questo è il numero totale di possibili configurazioni; quindi, , dove P è la classe di problemi risolvibili in tempo polinomiale da una macchina di Turing deterministica.
Ogni problema in L è completo nella riduzione in spazio logaritmico; dato che ciò risulta inutile, sono state definite riduzioni più deboli che permettono l'identificazione di problemi completi in L in modo più forte, ma non c'è una definizione universalmente accettata di problema L-completo.
Problemi aperti importanti sono le questioni ? e ?
La classe collegata di problemi costruttivi è FL. Si usa spesso FL per definire la riduzione in spazio logaritmico.
Nell'ottobre 2004, Omer Reingold in un articolo ha dimostrato che il problema di stabilire se c'è un percorso tra due vertici in un grafo non direzionato appartiene alla classe L, dimostrando che L = SL, poiché tale problema è SL-completo.
Come conseguenza di ciò, si ha una caratterizzazione logica semplice di L: contiene esattamente quei linguaggi esprimibili in logica del primo ordine con l'aggiunta di un operatore commutativo di chiusura transitiva (in termini di teoria dei grafi, ciò trasforma ogni componente connesso in una cricca).
Bibliografia
[modifica | modifica wikitesto]- Christos Papadimitriou, Computational Complexity, 1st edition, Addison Wesley, 1993, ISBN 0-201-53082-1. Chapter 16: Logarithmic space, pp.395–408.
- Undirected ST-connectivity in Log-Space. Omer Reingold. Electronic Colloquium on Computational Complexity. No. 94.
- Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997, ISBN 0-534-94728-X. Section 8.4: The Classes L and NL, pp.294–296.
- Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, ISBN 0-7167-1045-5. Section 7.5: Logarithmic Space, pp.177–181.
