L (計算複雑性理論)
あるLに属する問題がL完全であることを「Lに属するどんな問題も対数領域還元可能であること」と定義すると、 Lに属する全ての問題が「L完全」になってしまうので、あまり意味がない。より弱い還元を使う必要がある。
L = P や L = NL が正しいかどうかは未解決である。
関数問題に関する同様の計算量を FL という。FL は対数領域還元の定義によく使われる。
2004年10月、Omer Reingold は論文で USTCON 問題が L に属することを示した。USTCON問題とは、無向グラフで与えられた2点間の経路があるかどうかを判定する問題である。USTCON問題は、SLに属しSL完全であるため、L = SL であることが確定した。
この結果、L の性質として一階述語論理に推移閉包演算子を追加したもので表される言語が L に含まれることが判明した。
L は対数領域の神託(おおまかに言えば、対数領域を使う関数呼び出しに相当)を対数領域でシミュレート可能であり、各問合せに同じ領域を使用する。この性質をLがLに対して low であるという。