SL (計算複雑性理論)
深さ優先探索や幅優先探索といった古典的アルゴリズムは、USTCONを線形時間と線形領域で解くことができる。これらはSLが定義されるずっと以前からあり、SLがPに属することを証明している。USTCON(すなわちSL)はNLに属することも容易に示すことができる。
SLに関する自明でない成果は、1970年に証明されたサヴィッチの定理である。これにより、USTCON を log n 領域で解くアルゴリズムがもたらされた。しかし、深さ優先探索とは異なり、このアルゴリズムは時間に関しては多項式時間以上の時間がかかることがあり、実用的ではない。この結果から、USTCON およびSLは DSPACE(logn) に属することが示された。実際にはサヴィッチの定理はもっと広範囲なもので、NLが DSPACE(logn) に属することを示した。
決定性領域については、サヴィッチの定理以後22年間進歩が見られなかったが、1979年、Aleliunas らはUSTCONの実用的な確率的対数領域アルゴリズムを発見した。これは1つの頂点からランダムウォークし、|V| 回過ぎても解に到達しないときに受理しないとするアルゴリズムである。誤って拒絶する確率は小さく、ランダムウォークを継続するほど指数関数的にその確率が減少していく。これにより、SLはRLPに属することが示された。RLPとは、確率的チューリング機械で多項式時間と対数領域で解くことができ、誤って拒絶する確率は1/3未満とされる複雑性クラスである。