L (計算複雑性理論)
計算量理論においてLとは、決定性チューリングマシンで対数規模の領域(メモリ)を使って解くことができる決定問題の集合である。直観的には対数領域は、入力を参照するポインタを一定数保持するのに使われたり、対数個のブール値フラグを保持するのに使われたりする。
Lと関連する計算量にNLがある。NLは、非決定性チューリングマシン上で対数領域で決定可能な言語のクラスである。従って、 L ⊆ N L {\displaystyle \mathrm {L} \subseteq \mathrm {NL} } が成り立つ。
また、O(log n) の領域を使用する決定機械は時間 2=n 以内で停止するとしてよい。これは、対数領域の機械のとりうる状態の組み合わせの合計である。従って、 L ⊆ P {\displaystyle \mathrm {L} \subseteq \mathrm {P} } が成り立つ。ここで P は決定性チューリングマシンで多項式時間で解ける問題の集合である。
L完全の意味は還元の定め方が難しい。