Abstract
Directed st-connectivity is the problem of deciding whether or not there exists a path from a distinguished node s to a distinguished node t in a directed graph. We prove a timespace lower bound on the probabilistic NNJAG model of Poon [Proc. 34th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, 1993, pp. 218-227]. Let n be the number of nodes in the input graph and S and T be the space and time used by the NNJAG, respectively. We show that, for any δ > 0, if an NNJAG uses space S ∈ O(n1-δ), then T ∈ 2Ω(log2(n/S)); otherwise T ∈ 2Ωlog22(n log n/S)/log log n) × (nS/log n)1/2 preliminary version of this paper by Edmonds and Poon [Proc. 27th Annual ACM Symposium on Theory of Computing, Las Vegas, NV, 1995, pp. 147-156.], a lower bound of T ∈ 2Ωlog22(n log n/S)/log log n) × (nS/logn)1/2 was proved.) Our result greatly improves the previous lower bound of ST ∈ Ω(n2/logn) on the JAG model by Barnes and Edmonds [Proc. 34th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, 1993, pp. 228-237] and that of S1/3T ∈ Ω(n4/3) on the NNJAG model by Edmonds [Time-Space Lower Bounds for Undirected and Directed S T-Connectivity on JAG Models, Ph.D. thesis, University of Toronto, Toronto, ON, Canada, 1993]. Our lower bound is tight for S ∈ O(n1-δ), for any δ > 0, matching the upper bound of Barnes et al.[Proc. 7th Annual IEEE Conference on Structure in Complexity Theory, Boston, MA, 1992, pp. 27-331. As a corollary of this improved lower bound, we obtain the first tight space lower bound of Ω(log2 n) on the NNJAG model. No tight space lower bound was previously known even for the more restricted JAG model. © 1999 Society for Industrial and Applied Mathematics.
| Original language | English |
|---|---|
| Pages (from-to) | 2257-2284 |
| Journal | SIAM Journal on Computing |
| Volume | 28 |
| Issue number | 6 |
| DOIs | |
| Publication status | Published - 1999 |
Bibliographical note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].Research Keywords
- Connectivity
- Lower bounds
- Space complexity
- Space-time tradeoffs
Fingerprint
Dive into the research topics of 'Tight lower bounds for st-connectivity on the nnjag model'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver