En komputa komplikteorio, L estas komplikeca klaso de decidaj problemoj, kiuj povas esti solvitaj per determinisma maŝino de Turing kun uzo de logaritma kvanto de memora spaco. Intuicie, logaritma spaco estas spaco sufiĉa por konservi konstantan kvanton de nadloj en la enigo kaj logaritman kvanton de buleaj flagoj.

Ĝeneraligo de L estas NL, kiu estas klaso de lingvoj decideblaj en logaritma spaco per determinisma maŝino de Turing. Tiam ${\displaystyle \mathrm {L} \subseteq \mathrm {NL} }$.

P estas minimume same granda kiel L, la klaso de problemoj decidebla en logaritma kvanto de memora spaco. Kun uzo de spaco O(log n) ne povas esti uzata tempo pli grandan ol 2^{O(log n)} = n^O(1), ĉar ĉi tio estas la entuta kvanto de eblaj konfiguroj, konservataj en la memoro. Poste ĉi tia kvanto de paŝoj la algoritmo devas nepre aŭ finiĝi aŭ ripetiĝi de iu jam estinta stato kaj tiel neniam finiĝi. Tial, L estas subaro de P. Ne estas sciata, ĉu L = P.

'Ĉu L = P ?' kaj 'ĉu L = NL ?' estas gravaj malfermitaj problemoj.

Plua klasifiko de problemoj en L - kiel pli forte plenaj aŭ pli forte plenaj en L - estas interesa. Ĉiu problemo en L estas plena sub log-spaca malpligrandiĝo. Tiel pro tio ke log-spaca malpligrandiĝo estas ne taŭga, pli malfortaj malpligrandiĝoj estas difinitaj. Sed tamen ne estas ĝenerale akceptita difino de L-pleneco.

La rilatanta klaso de funkciaj problemoj estas FL. FL estas ofte uzata por difini log-spacan malpligrandiĝon.

Omer Reingold en oktobro de 2004 montris, ke USTCON, la problemo de 'ĉu tie ekzistas vojo inter du verticoj en donita sendirekta grafeo?' (vd. st-connectivity), estas en L, kaj do L = SL, ĉar la problemo estas SL-plena.

Unu konsekvenco de ĉi tio estas simpla logika karakterizado de L: ĝi enhavas precize tiuj lingvoj kiuj estas esprimeblaj en unua-ordo logiko kun aldonita komuta transita ferma operatoro (en grafeteoriaj terminoj, ĉi tiu operatoro reformigas ĉiun koneksan komponanton en klikon).

L estas malalta por sin, ĉar ĝi povas simuli log-spacaj orakolajn demandojn (malglate parolante, "funkciajn vokojn kiu uzas logaritman spacon") en logaritma spaco, reuzanta la saman spacon por ĉiu demando.

• Omer Reingold
• (al anglalingva fonto: 2006

• Undirected ST-connectivity in Log-Space - Nedirektita ST-konekteco en log-spaco. Omer Reingold. Electronic Colloquium on Computational Complexity - Elektronika Kolokvo sur Komputa Komplikeco. No. 94.