計算複雑性理論の研究により、このクラスと他の複雑性クラスの関係が明らかとなり、必要な計算資源も明らかとなってきた。一方、アルゴリズムの研究によって、対数領域で解ける問題も明らかとなってきつつある。しかし、計算複雑性理論の他の分野と同様、NLについての重要な部分は未解決である。
ある複雑性クラスに属する最も難しい問題を指して完全問題という。直観的には、完全問題を効率的に解く方法が判っていれば、それを使ってそのクラスのあらゆる問題を解くことが出来る。すなわち、完全問題はその複雑性クラスの能力の程度を示すものである。
このようなクラスは は時間が多項式時間に制限されていない。なぜなら、対数領域の状態の組み合わせがたかだか多項式で表せるほどしかないとしても、確率的な解法であるために無限ループに陥る可能性があるからである。これを多項式時間に制限すると という別のクラスになる。