Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-097 | 15th June 2016 07:30

Trading Determinism for Time in Space Bounded Computations

RSS-Feed




TR16-097
Authors: Vivek Anand T Kallampally, Raghunath Tewari
Publication: 15th June 2016 08:17
Downloads: 1071
Keywords: 


Abstract:

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 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.



ISSN 1433-8092 | Imprint