e/SL (complexity)

Information
has gloss	eng: In computational complexity theory, SL (Symmetric Logspace or Sym-L) is the complexity class of problems log-space reducible to USTCON (undirected s-t connectivity), which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the same connected component. This problem is also called the undirected reachability problem. It does not matter whether many-one reducibility or Turing reducibility is used. Although originally described in terms of symmetric Turing machines, that equivalent formulation is very complex, and the reducibility definition is what is used in practice.
lexicalization	eng: SL
instance of	e/Complexity class

Meaning
Japanese
has gloss	jpn: 計算複雑性理論におけるSLとは、USTCON問題に対数領域還元可能な問題の複雑性クラスである（Symmetric Logspace の略）。USTCON問題とは、無向グラフの2点間に経路があるかどうかを判定する問題であり、言い換えれば2つの頂点が同じ連結部分に属しているかどうかを判定する問題である。多対一還元かチューリング還元かは問われない。本来は「対称性チューリング機械」を使って記述され、そのような定式化は非常に複雑であるが、還元性の定義は実際に使われているものである。
lexicalization	jpn: SL
Castilian
has gloss	spa: En teoría de la complejidad computacional, la clase de complejidad SL (espacio logarítmico simétrico, del inglés Symmetric Logspace o Sym-L) es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing no determinista en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada, tal que: #Si la respuesta es positiva, existe uno o más cómputos de la máquina que aceptan. #Si la respuesta es negativa, todos los cómputos de la máquina rechazan la entrada. #Si la máquina puede hacer una transición no determinista entre una configuración A y una configuración B, también puede hacer una transición de B hacia A (condición de simetría).
lexicalization	spa: SL