Time-space lower bounds for undirected and directed ST-connectivity on jag models
Jeff A. Edmonds · 1993
Directed and undirected st-connectivity are important problems in computing. There are algorithms for the undirected case that use O (n) time and algorithms that use O (log n) space. The first result of this thesis proves that, in a very natural structured model, the JAG (Jumping Automata for Graphs), these upper bounds are not simultaneously achievable. This uses new entropy techniques to prove tight bounds on a game involving a helper and a player that models a computation having precomputed information about the input stored in its bounded space. The second result proves that a JAG requires a time-space tradeoff of T \\Theta S 1 2 2\\Omega i mn 1 2 j to compute directed st-connectivity. The third result proves a time-space tradeoff of T \\Theta S 1 3 2\\Omega i m 2 3 n 2 3 j on a version of the...