NL完全

在計算複雜性理論中，NL完全是由全體對NL類完備的語言構成的複雜性類。也就是說，NL完全的語言是NL類中最「難解」和最「有力」的語言。如果有某個確定性的方法可以在對數空間內解決一個NL完全問題，那麼就會有NL=L。

定義

在全體判定問題中，NL類包含了那些可以用非確定型圖靈機在對數空間內解決的問題。這裡的圖靈機要求有一條只讀輸入帶，和另一條空間上限與輸入長度的對數成比例的讀寫帶。類似地，L類包含了可以用同樣結構的確定型圖靈機解決的判定問題。由於這種圖靈機的格局數目只有多項式級別，因此NL和L都是P的子集。

正式地說，一個問題是NL完全的，當且僅當它屬於NL，並且所有NL中的判定問題都可以Log-空間規約到它。