NL (計算複雑性理論)
NL(えぬえる、英: Nondeterministic Logarithmic-space)は、計算複雑性理論における決定問題の複雑性クラスの一つである。非決定性チューリングマシンで対数規模の記憶領域を使って解ける問題がこのクラスに属する。
NL は Lを一般化したものである。L は決定性チューリングマシンでの対数領域問題のクラスである。決定性チューリングマシンは非決定性チューリングマシンに含まれるため、L も NL に含まれる。
NLは非決定性領域(NSPACE)の計算資源記法で形式的に定義でき、NL = NSPACE(log n) となる。
計算複雑性理論の研究により、このクラスと他の複雑性クラスの関係が明らかとなり、必要な計算資源も明らかとなってきた。一方、アルゴリズムの研究によって、対数領域で解ける問題も明らかとなってきつつある。しかし、計算複雑性理論の他の分野と同様、NLについての重要な部分は未解決である。
NLの確率的定義(後述)を指して RL と呼ぶこともある。しかし、RLという名称はRLPという複雑性クラスの別名として使われることが多い(RLPとは、確率的チューリングマシンで対数領域と多項式時間で解ける問題のクラス)。