Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/SL_(complexity)> ?p ?o }
Showing triples 1 to 59 of
59
with 100 triples per page.
- SL_(complexity) abstract "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.".
- SL_(complexity) wikiPageID "1174919".
- SL_(complexity) wikiPageLength "12943".
- SL_(complexity) wikiPageOutDegree "45".
- SL_(complexity) wikiPageRevisionID "579753024".
- SL_(complexity) wikiPageWikiLink Advice_(complexity).
- SL_(complexity) wikiPageWikiLink Avi_Wigderson.
- SL_(complexity) wikiPageWikiLink Bipartite_graph.
- SL_(complexity) wikiPageWikiLink Boolean_satisfiability_problem.
- SL_(complexity) wikiPageWikiLink Breadth-first_search.
- SL_(complexity) wikiPageWikiLink Category:Complexity_classes.
- SL_(complexity) wikiPageWikiLink Christos_Papadimitriou.
- SL_(complexity) wikiPageWikiLink Complement_(complexity).
- SL_(complexity) wikiPageWikiLink Complexity_class.
- SL_(complexity) wikiPageWikiLink Computational_complexity_theory.
- SL_(complexity) wikiPageWikiLink Connected_component_(graph_theory).
- SL_(complexity) wikiPageWikiLink Depth-first_search.
- SL_(complexity) wikiPageWikiLink Directed_graph.
- SL_(complexity) wikiPageWikiLink Endre_Szemerédi.
- SL_(complexity) wikiPageWikiLink Exclusive_or.
- SL_(complexity) wikiPageWikiLink Graph_(discrete_mathematics).
- SL_(complexity) wikiPageWikiLink Graph_coloring.
- SL_(complexity) wikiPageWikiLink Graph_theory.
- SL_(complexity) wikiPageWikiLink poly.
- SL_(complexity) wikiPageWikiLink L_(complexity).
- SL_(complexity) wikiPageWikiLink Log-space_reduction.
- SL_(complexity) wikiPageWikiLink Many-one_reduction.
- SL_(complexity) wikiPageWikiLink Michael_Sipser.
- SL_(complexity) wikiPageWikiLink Minimum_spanning_tree.
- SL_(complexity) wikiPageWikiLink NL_(complexity).
- SL_(complexity) wikiPageWikiLink Noam_Nisan.
- SL_(complexity) wikiPageWikiLink Non-deterministic_Turing_machine.
- SL_(complexity) wikiPageWikiLink Omer_Reingold.
- SL_(complexity) wikiPageWikiLink Oracle_machine.
- SL_(complexity) wikiPageWikiLink RL_(complexity).
- SL_(complexity) wikiPageWikiLink Savitchs_theorem.
- SL_(complexity) wikiPageWikiLink Spanning_tree.
- SL_(complexity) wikiPageWikiLink St-connectivity.
- SL_(complexity) wikiPageWikiLink Symmetric_Turing_machine.
- SL_(complexity) wikiPageWikiLink Turing_machine.
- SL_(complexity) wikiPageWikiLink Turing_reduction.
- SL_(complexity) wikiPageWikiLink ZPLP.
- SL_(complexity) wikiPageWikiLinkText "SL (complexity)".
- SL_(complexity) wikiPageWikiLinkText "SL".
- SL_(complexity) wikiPageWikiLinkText "symmetric logspace".
- SL_(complexity) wikiPageUsesTemplate Template:ComplexityClasses.
- SL_(complexity) subject Category:Complexity_classes.
- SL_(complexity) hypernym Class.
- SL_(complexity) type Class.
- SL_(complexity) comment "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.".
- SL_(complexity) label "SL (complexity)".
- SL_(complexity) sameAs Q6138961.
- SL_(complexity) sameAs إس_إل_(تعقيد_حسابي).
- SL_(complexity) sameAs SL_(clase_de_complejidad).
- SL_(complexity) sameAs SL_(計算複雑性理論).
- SL_(complexity) sameAs m.04djrd.
- SL_(complexity) sameAs Q6138961.
- SL_(complexity) wasDerivedFrom SL_(complexity)?oldid=579753024.
- SL_(complexity) isPrimaryTopicOf SL_(complexity).