Trading determinism for time in space bounded computations
From MaRDI portal
Publication:4608568
DOI10.4230/LIPICS.MFCS.2016.10zbMATH Open1398.68183arXiv1606.04649MaRDI QIDQ4608568FDOQ4608568
Authors: Vivek Anand T. Kallampally, Raghunath Tewari 
Publication date: 21 March 2018
Full work available at URL: https://arxiv.org/abs/1606.04649
Recommendations
- If deterministic and nondeterministic space complexities are equal for \(\log \log n\) then they are also equal for \(\log n\)
- Time-space tradeoffs for satisfiability
- Making Nondeterminism Unambiguous
- On efficient deterministic simulation of turing machine computations below logaspace
- Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space
Cited In (13)
- Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space
- Title not available (Why is that?)
- Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
- Determinism versus nondeterminism for linear time RAMs with memory restrictions
- Derandomizing isolation in space-bounded settings
- Bipartite perfect matching is in quasi-NC
- Making Nondeterminism Unambiguous
- Pseudodeterministic algorithms and the structure of probabilistic time
- If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n
- Isolating a vertex via lattices: polytopes with totally unimodular faces
- Isolating a vertex via lattices: polytopes with totally unimodular faces
- Compressed Decision Problems in Hyperbolic Groups.
- Time-space tradeoffs for computing functions, using connectivity properties of their circuits
This page was built for publication: Trading determinism for time in space bounded computations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608568)
