SL (complexity) (original) (raw)
En teoria de la complexitat, la classe de complexitat SL és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en espai log(n) tal que: * si la resposta és SI, existeix algun camí de còmput que accepta l'entrada * si la resposta és NO, tots els canins han rebutjat l'entrada * si la màquina pot fer una transició no determinista entre una configuració A i una configuració B, també pot fer la transició simètrica (fer una transició entre la configuració B a la configuració A). Aquesta màquina es coneix com a màquina de Turing simètrica.
| Property | Value |
|---|---|
| dbo:abstract | En teoria de la complexitat, la classe de complexitat SL és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en espai log(n) tal que: * si la resposta és SI, existeix algun camí de còmput que accepta l'entrada * si la resposta és NO, tots els canins han rebutjat l'entrada * si la màquina pot fer una transició no determinista entre una configuració A i una configuració B, també pot fer la transició simètrica (fer una transició entre la configuració B a la configuració A). Aquesta màquina es coneix com a màquina de Turing simètrica. (ca) في علم التعقيد الحسابي SL هي قسم المسائل التي يمكن اختصارها لمسألة USTCON بواسطة اختصار سعة موارده لوجاريثمية، وهذه المسألة هي هل يوجد مسار بين الرأسين s و- t في مخطط غير موجه؟ هذه المسألة حسب التعريف هي SL كاملة. هذه المسألة هي حالة خاصة من المسألة STCON والتي تُعنى بإيجاد مسار بين الرأسين s و- t في مخطط موجه، هذه المسألة الأكثر عمومية هي مسألة NL كاملة. في أكتوبر 2004 عومِر راين-جولد برهن أنَّ SL=L . (ar) 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: 1. * Si la respuesta es positiva, existe uno o más cómputos de la máquina que aceptan. 2. * Si la respuesta es negativa, todos los cómputos de la máquina rechazan la entrada. 3. * 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). En 2004 se demostró que esta clase de complejidad es equivalente a L. En otras palabras, la condición de simetría en la máquina de Turing no determinista la hace equivalente a una máquina de Turing determinista. (es) 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. USTCON is a special case of STCON (directed reachability), the problem of determining whether a directed path between two vertices in a directed graph exists, which is complete for NL. Because USTCON is SL-complete, most advances that impact USTCON have also impacted SL. Thus they are connected, and discussed together. In October 2004 Omer Reingold showed that SL = L. (en) 計算複雑性理論におけるSLとは、USTCON問題に対数領域還元可能な問題の複雑性クラスである（Symmetric Logspace の略）。USTCON問題とは、無向グラフの2点間に経路があるかどうかを判定する問題であり、言い換えれば2つの頂点が同じ連結部分に属しているかどうかを判定する問題である。多対一還元かチューリング還元かは問われない。SLは本来は「対称性チューリング機械」を使って定義されるが、非常に複雑な定式化であるため、実際にはUSTCON問題への還元性の方がよく使われる。 USTCON は （有向到達可能性）問題の特殊ケースである。STCONは有向グラフでの2つの頂点間の経路の有無を判定する問題であり、NL-完全である。USTCON は SL-完全なので、USTCONの解法の進歩は SL にも影響がある。 2004年10月、Omer Reigngold は SL = L であることを示した。 (ja) Na teoria da complexidade computacional, SL (Logspace Simétrica ou Sym-L) é a classe de complexidade dos problemas de log-espaço redutível a USTCON (não-s-t conectividade), é o problema de determinar se existe um caminho entre dois vértices em um grafo não direcionado, caso contrário, descrito como o problema de determinar se dois vértices estão no mesmo componente conectado. Este problema também é chamado de problema da não-acessibilidade. Embora originalmente descrita em termos de máquinas simétricas de Turing, é equivalente a formulação uma muito complexa, e a definição de redutibilidade é o que é usado na prática. USTCON é um caso especial de STCON (acessibilidade dirigida), o problema de determinar se um caminho dirigido entre dois vértices em um grafo direcionado existe, que é completa para o NL. USTCON é SL-completa, a maioria dos avanços mostram que o impacto USTCON têm também um impacto SL. Assim, eles são conectados, e discutidos em conjunto. Em outubro de 2004 Omer Reingold mostrou que SL = L. (pt) |
| dbo:wikiPageID | 1174919 (xsd:integer) |
| dbo:wikiPageLength | 14117 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1041330865 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Nondeterministic_Turing_machines dbr:STCON dbr:Undirected_graph dbr:Depth-first_search dbr:L/poly dbr:Oracle_machine dbr:Christos_Papadimitriou dbr:Endre_Szemerédi dbr:Graph_coloring dbr:NL_(complexity) dbr:L_(complexity) dbr:Complement_(complexity) dbr:Complexity_class dbr:Computational_complexity_theory dbr:Many-one_reduction dbr:Avi_Wigderson dbr:Log-space_reduction dbr:Exclusive_or dbr:Breadth-first_search dbr:Noam_Nisan dbr:Directed_graph dbr:Graph_theory dbr:RL_(complexity) dbc:Complexity_classes dbr:Harry_R._Lewis dbr:Advice_(complexity) dbr:Bipartite_graph dbr:Boolean_satisfiability_problem dbr:Connected_component_(graph_theory) dbr:Michael_Sipser dbr:Omer_Reingold dbr:Random_walk dbr:Symmetric_Turing_machine dbr:Spanning_forest dbr:Turing_reduction dbr:Savitch's_theorem dbr:Christos_H._Papadimitriou dbr:Minimum_weight_spanning_forest dbr:Deterministic_Turing_machine dbr:Log-space_reducible dbr:ZPLP |
| dbp:wikiPageUsesTemplate | dbt:Math dbt:Var dbt:Isbn dbt:Sans-serif dbt:Abs dbt:ComplexityClasses |
| dct:subject | dbc:Complexity_classes |
| gold:hypernym | dbr:Class |
| rdf:type | yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264 |
| rdfs:comment | En teoria de la complexitat, la classe de complexitat SL és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en espai log(n) tal que: * si la resposta és SI, existeix algun camí de còmput que accepta l'entrada * si la resposta és NO, tots els canins han rebutjat l'entrada * si la màquina pot fer una transició no determinista entre una configuració A i una configuració B, també pot fer la transició simètrica (fer una transició entre la configuració B a la configuració A). Aquesta màquina es coneix com a màquina de Turing simètrica. (ca) في علم التعقيد الحسابي SL هي قسم المسائل التي يمكن اختصارها لمسألة USTCON بواسطة اختصار سعة موارده لوجاريثمية، وهذه المسألة هي هل يوجد مسار بين الرأسين s و- t في مخطط غير موجه؟ هذه المسألة حسب التعريف هي SL كاملة. هذه المسألة هي حالة خاصة من المسألة STCON والتي تُعنى بإيجاد مسار بين الرأسين s و- t في مخطط موجه، هذه المسألة الأكثر عمومية هي مسألة NL كاملة. في أكتوبر 2004 عومِر راين-جولد برهن أنَّ SL=L . (ar) 計算複雑性理論におけるSLとは、USTCON問題に対数領域還元可能な問題の複雑性クラスである（Symmetric Logspace の略）。USTCON問題とは、無向グラフの2点間に経路があるかどうかを判定する問題であり、言い換えれば2つの頂点が同じ連結部分に属しているかどうかを判定する問題である。多対一還元かチューリング還元かは問われない。SLは本来は「対称性チューリング機械」を使って定義されるが、非常に複雑な定式化であるため、実際にはUSTCON問題への還元性の方がよく使われる。 USTCON は （有向到達可能性）問題の特殊ケースである。STCONは有向グラフでの2つの頂点間の経路の有無を判定する問題であり、NL-完全である。USTCON は SL-完全なので、USTCONの解法の進歩は SL にも影響がある。 2004年10月、Omer Reigngold は SL = L であることを示した。 (ja) 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: En 2004 se demostró que esta clase de complejidad es equivalente a L. En otras palabras, la condición de simetría en la máquina de Turing no determinista la hace equivalente a una máquina de Turing determinista. (es) 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. (en) Na teoria da complexidade computacional, SL (Logspace Simétrica ou Sym-L) é a classe de complexidade dos problemas de log-espaço redutível a USTCON (não-s-t conectividade), é o problema de determinar se existe um caminho entre dois vértices em um grafo não direcionado, caso contrário, descrito como o problema de determinar se dois vértices estão no mesmo componente conectado. Este problema também é chamado de problema da não-acessibilidade. Embora originalmente descrita em termos de máquinas simétricas de Turing, é equivalente a formulação uma muito complexa, e a definição de redutibilidade é o que é usado na prática. (pt) |
| rdfs:label | إس إل (تعقيد حسابي) (ar) SL (Complexitat) (ca) SL (clase de complejidad) (es) SL (計算複雑性理論) (ja) SL (complexity) (en) Complexidade SL (pt) |
| owl:sameAs | freebase:SL (complexity) yago-res:SL (complexity) wikidata:SL (complexity) dbpedia-ar:SL (complexity) dbpedia-ca:SL (complexity) dbpedia-es:SL (complexity) dbpedia-ja:SL (complexity) dbpedia-pt:SL (complexity) https://global.dbpedia.org/id/4nzv9 |
| prov:wasDerivedFrom | wikipedia-en:SL_(complexity)?oldid=1041330865&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:SL_(complexity) |
| is dbo:wikiPageDisambiguates of | dbr:SL |
| is dbo:wikiPageRedirects of | dbr:USTCON dbr:Sym-L dbr:Symmetric_Logspace dbr:Symmetric_log-space dbr:Symmetric_log_space dbr:Symmetric_logspace dbr:Undirected_reachability dbr:Undirected_reachability_problem |
| is dbo:wikiPageWikiLink of | dbr:List_of_complexity_classes dbr:Richard_Lipton dbr:L/poly dbr:Connectivity_(graph_theory) dbr:Salil_Vadhan dbr:L_(complexity) dbr:Zig-zag_product dbr:Complement_(complexity) dbr:Component_(graph_theory) dbr:Symmetric_space_(disambiguation) dbr:Log-space_reduction dbr:Expander_graph dbr:RL_(complexity) dbr:Harry_R._Lewis dbr:Boolean_satisfiability_problem dbr:St-connectivity dbr:Implicit_graph dbr:In-place_algorithm dbr:SL dbr:Symmetric_Turing_machine dbr:USTCON dbr:Sym-L dbr:Symmetric_Logspace dbr:Symmetric_log-space dbr:Symmetric_log_space dbr:Symmetric_logspace dbr:Undirected_reachability dbr:Undirected_reachability_problem |
| is foaf:primaryTopic of | wikipedia-en:SL_(complexity) |