ECCC-Report TR16-097https://eccc.weizmann.ac.il/report/2016/097Comments and Revisions published for TR16-097en-usWed, 15 Jun 2016 08:17:29 +0300
Paper TR16-097
| Trading Determinism for Time in Space Bounded Computations |
Raghunath Tewari,
Vivek Anand T Kallampally
https://eccc.weizmann.ac.il/report/2016/097Savitch showed in $1970$ that nondeterministic logspace (NL) is contained in deterministic $\mathcal{O}(\log^2 n)$ space but his algorithm requires quasipolynomial time. The question whether we can have a deterministic algorithm for every problem in NL that requires polylogarithmic space and simultaneously runs in polynomial time was left open.
In this paper we give a partial solution to this problem and show that for every language in NL there exists an unambiguous nondeterministic algorithm that requires $\mathcal{O}(\log^2 n)$ space and simultaneously runs in polynomial time.
Wed, 15 Jun 2016 08:17:29 +0300https://eccc.weizmann.ac.il/report/2016/097