About: SL (計算複雑性理論)

計算複雑性理論におけるSLとは、USTCON問題に対数領域還元可能な問題の複雑性クラスである（Symmetric Logspace の略）。USTCON問題とは、無向グラフの2点間に経路があるかどうかを判定する問題であり、言い換えれば2つの頂点が同じ連結部分に属しているかどうかを判定する問題である。多対一還元かチューリング還元かは問われない。SLは本来は「対称性チューリング機械」を使って定義されるが、非常に複雑な定式化であるため、実際にはUSTCON問題への還元性の方がよく使われる。 USTCON は （有向到達可能性）問題の特殊ケースである。STCONは有向グラフでの2つの頂点間の経路の有無を判定する問題であり、NL-完全である。USTCON は SL-完全なので、USTCONの解法の進歩は SL にも影響がある。 2004年10月、Omer Reigngold は SL = L であることを示した。