Metraipolis › archive › dc_cc2dcabba78d

L (complessità) — Wikipedia

Source: Wikipedia (it)
Original: https://it.wikipedia.org/wiki/L_(complessit%C3%A0)
License (as archived): CC-BY-SA-4.0
Archived: 2026-10-07T16:43:55.989Z
SHA-256 of the archived text: 7bbd7c429b0f3941df80f246478d33a08220bba2c36049128a4618e667ac6fa3
Stable URL of this page: https://metraipolis.com/documento/dc_cc2dcabba78d

How to cite

L (complessità) — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/L_(complessit%C3%A0) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_cc2dcabba78d (Metraipolis archive dc_cc2dcabba78d, sha256 7bbd7c429b0f3941df80f246478d33a08220bba2c36049128a4618e667ac6fa3)

BibTeX

@misc{dccc2dcabba78d,
  title = {L (complessità) — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/L_(complessit%C3%A0)},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_cc2dcabba78d; sha256 7bbd7c429b0f3941df80f246478d33a08220bba2c36049128a4618e667ac6fa3},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/L_(complessit%C3%A0). Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 L ⊆ NL {\displaystyle L\subseteq {\mbox{NL}}} . Inoltre, un decisore che usa spazio O ( log n ) {\displaystyle O(\log n)} non può impiegare un tempo superiore a 2 O ( log n ) = n O ( 1 ) {\displaystyle 2^{O(\log n)}=n^{O(1)}} , poiché questo è il numero totale di possibili configurazioni; quindi, L ⊆ P {\displaystyle L\subseteq P} , 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 L = P {\displaystyle L=P} ? e L = N L {\displaystyle L=NL} ? 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).

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoria dei grafi»).
Fonte: Wikipedia in italiano, voce «L (complessità)» — https://it.wikipedia.org/wiki/L_(complessit%C3%A0)
Wikidata Q1192782 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1192782
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/L_(complessit%C3%A0)?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 152780488, consultata il 2026-10-07T16:12:17.743Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: ac75c6bc9f1141b52e049d83f62c19ef7ac4d8482b1dadc604c7f25a9176a6aa