Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with unambiguous nondeterminism:
TR16-097 | 15th June 2016
Vivek Anand T Kallampally, Raghunath Tewari

Trading Determinism for Time in Space Bounded Computations

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

TR17-052 | 19th March 2017
Dieter van Melkebeek, Gautam Prakriya

Derandomizing Isolation in Space-Bounded Settings

We study the possibility of deterministic and randomness-efficient isolation in space-bounded models of computation: Can one efficiently reduce instances of computational problems to equivalent instances that have at most one solution? We present results for the NL-complete problem of reachability on digraphs, and for the LogCFL-complete problem of certifying acceptance ... more >>>

ISSN 1433-8092 | Imprint