Trading Determinism for Time in Space Bounded Computations

Vivek Anand T Kallampally, Raghunath Tewari

Savitch showed in $1970$ that nondeterministic logspace (NL) is contained in deterministic $\mathcal{O}({\log }^{2}n)$ space but his algorithm requires quasipolynomial time. The questi…