SL (計算複雑性理論)
L = SL であることが判明したことで様々な影響が生じた。明らかに SL-完全問題が全て L に属することになり、全て決定性の対数領域/多項式領域のアルゴリズムで効率的に解ける可能性が示された。特に対数領域還元の利用範囲が広がったと言える。また、USTCON に対数領域還元可能な問題が L に属すると定義されるようになった。
1982年、Lewis と クリストス・パパディミトリウ によってSLが最初に定義された。彼らはUSTCONの属する複雑性クラスを探していて、当時は非決定性が必要とされないにもかかわらず NL とされていた。彼らは「対称性チューリング機械」を定義してSLを定義し、USTCONがSL-完全であることを示し、次が成り立つことを証明した。
L ⊆ S L ⊆ N L {\displaystyle \mathrm {L} \subseteq \mathrm {SL} \subseteq \mathrm {NL} }
ここで、Lは通常のチューリング機械で対数領域で解ける問題のクラスであり、NLは非決定性チューリング機械で対数領域で解ける問題のクラスである。後述するように Reingold は、対数領域に限定したとき、対称性チューリング機械と通常の決定性チューリング機械の能力が同じであるという事実を示した。
1989年、Borodin らはこの結果を出発点として、USTCONの補問題(2つの頂点が別の連結部分に属するか)もRLPに属することを示した。これにより、USTCONおよびSLは co-RLP にも属することになり、RLP と co-RLP の交差である ZPLP に属することが明らかとなった。ZPLP は、対数領域でかつ多項式時間が期待されるラスベガス法で解ける問題のクラスである。
1992年、Nisan、Szemerédi、Wigderson は USTCON を log n の領域で解ける決定性の新たなアルゴリズムを発見した。その後、若干の改良が加えられている。
1995年、Nisan と Ta-Shma は、SL が補問題について閉じていること(すなわち SL = co-SL)を示した。当時、SL と co-SL は異なると考えられていた。
SL = co-SL の重要な系の1つとして、L = SL がある。すなわち、決定性の対数領域を持つチューリング機械にSLの神託機械を付加すると、SLに属する問題は明らかに解けるが、それ以外の問題は解けない。これは、ある問題がSLに属することを示すのに、チューリング還元でも多対一還元でもよいということを示している。
2004年10月、Omer Reigngold は USTCON が実際には Lに属することを示した。USTCON は SL-完全とされていたため、この事実によって SL = L であることが判明した。数週間後、Vladimir Trifonov は USTCON を O(log n log log n) 領域で解く決定性のアルゴリズムを示した。