NL完全
此條目沒有列出任何參考或來源。 (2013年10月21日) |
在計算複雜性理論中,NL完全是由全體對NL類完備的語言構成的複雜性類。也就是說,NL完全的語言是NL類中最「難解」和最「有力」的語言。如果有某個確定性的方法可以在對數空間內解決一個NL完全問題,那麼就會有NL=L。
定義
在全體判定問題中,NL類包含了那些可以用非確定型圖靈機在對數空間內解決的問題。這裡的圖靈機要求有一條只讀輸入帶,和另一條空間上限與輸入長度的對數成比例的讀寫帶。類似地,L類包含了可以用同樣結構的確定型圖靈機解決的判定問題。由於這種圖靈機的格局數目只有多項式級別,因此NL和L都是P的子集。
正式地說,一個問題是NL完全的,若且唯若它屬於NL,並且所有NL中的判定問題都可以Log-空間規約到它。