Trading determinism for time in space bounded computations
From MaRDI portal
Publication:4608568
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
- scientific article; zbMATH DE number 3883610 (Why is no real title available?)
- 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
- If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n
- Pseudodeterministic algorithms and the structure of probabilistic time
- 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)
