Undirected connectivity in log-space
E591745
"Undirected connectivity in log-space" is a landmark theoretical computer science paper by Omer Reingold that proved the complexity classes L and SL are equal by giving a deterministic log-space algorithm for undirected graph connectivity.
Statements (42)
| Predicate | Object |
|---|---|
| instanceOf | academic paper ⓘ |
| author | Omer Reingold NERFINISHED ⓘ |
| complexityClassRelation |
L = SL
ⓘ
L ⊆ SL ⓘ SL ⊆ L ⓘ |
| field |
computational complexity theory
ⓘ
theoretical computer science ⓘ |
| hasAlgorithmProperty |
logarithmic space complexity
ⓘ
polynomial time complexity ⓘ |
| implies | randomness is not needed for solving undirected connectivity in logarithmic space ⓘ |
| influencedArea |
construction of expander graphs
ⓘ
derandomization of space-bounded algorithms ⓘ log-space algorithm design ⓘ |
| introducesOrDevelops | use of zig-zag product for space-bounded derandomization ⓘ |
| mainResult |
L = SL
ⓘ
existence of a deterministic log-space algorithm for undirected graph connectivity ⓘ |
| problemAddressed | undirected graph connectivity ⓘ |
| proves |
every undirected graph connectivity instance can be solved in O(log n) space deterministically
ⓘ
existence of a deterministic log-space algorithm for undirected s-t connectivity ⓘ |
| relatedConcept |
L
ⓘ
NL ⓘ RL NERFINISHED ⓘ SL ⓘ |
| relatedProblem |
directed graph connectivity
ⓘ
s-t connectivity ⓘ |
| resultType |
complexity class collapse
ⓘ
derandomization result ⓘ |
| shows |
symmetric log-space SL collapses to deterministic log-space L
ⓘ
undirected connectivity is solvable in deterministic logarithmic space without randomness ⓘ undirected s-t connectivity is complete for L under log-space reductions ⓘ |
| significance |
established that SL does not provide more power than L for undirected connectivity
ⓘ
landmark result in the study of log-space complexity classes ⓘ resolved a long-standing open problem in complexity theory about the power of randomness in space-bounded computation ⓘ |
| topic |
derandomization
ⓘ
graph connectivity ⓘ logarithmic space algorithms ⓘ space complexity classes ⓘ space-bounded computation ⓘ |
| usesTechnique |
expander graphs
ⓘ
graph derandomization ⓘ zig-zag product of graphs ⓘ |
| yearAnnounced | early 2000s ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.