SL (計算複雑性理論)
定義から、USTCON は明らかにSL-完全である(SLに属する問題は全てUSTCONに還元可能である)。USTCONに直接あるいは間接に還元することで様々な完全問題が見つかり、Àlvarez と Greenlaw がそれらをまとめた。その多くはグラフ理論における問題である。主なものを以下に列挙する。
USTCON
対称性チューリング機械のシミュレーション: 対称性チューリング機械にある領域を与えたとき、ある入力を受理するか?
点素な道(経路): USTCON を経路長について一般化したもの
2部グラフかどうかの判定、またはグラフを2色でグラフ彩色できるか?
2つの無向グラフが同数の連結部分を持つか?
グラフの連結部分が偶数個あるか?
グラフの中のある枝について、それを含む輪があるか?
2つのグラフのスパニング木の枝数が同じか?
グラフの各枝にそれぞれ異なる重み付けがされているとき、ある枝が最小重みスパニング森に含まれるか?
排他的論理和 2-充足可能性問題: 変項の対 (xi,xj) がいくつかあって、それらについて xi xor xj が成り立つ必要があるとき、全体が真となるような変項の値の組み合わせがあるか?
これらの補問題もSLに属する。すなわち、SLは補問題について閉じている。
既に L = SL であることは分かっているので、対数領域還元によってさらに多数のSL-完全問題があることがわかっている。LまたはSLに属する問題は全てSL-完全であり、L-完全とSL-完全は等価である。そういった意味で複雑性クラスとしてはあまり重要ではなくなっている。