2026-07-20T11:16:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6426 2024-03-06T10:38:14Z ddc:004 open_access

Trading Determinism for Time in Space Bounded Computations Kallampally, Vivek Anand T Tewari, Raghunath space complexity unambiguous computations Savitch's Theorem Savitch showed in 1970 that nondeterministic logspace (NL) is contained in deterministic 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 O(log^2(n)) space and simultaneously runs in polynomial time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vivek Anand T Kallampally and Raghunath Tewari 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.10 urn:nbn:de:0030-drops-64268 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.10 eng https://creativecommons.org/licenses/by/3.0/legalcode