Trading determinism for time in space bounded computations
From MaRDI portal
Recommendations
- If deterministic and nondeterministic space complexities are equal for n then they are also equal for 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
(15)- Determinism versus nondeterminism for linear time RAMs with memory restrictions
- scientific article; zbMATH DE number 3883610 (Why is no real title available?)
- Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space
- Making Nondeterminism Unambiguous
- Bipartite perfect matching is in quasi-NC
- Isolating a vertex via lattices: polytopes with totally unimodular faces
- Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
- Compressed Decision Problems in Hyperbolic Groups.
- Derandomizing isolation in space-bounded settings
- Time-space tradeoffs for computing functions, using connectivity properties of their circuits
- Isolating a vertex via lattices: polytopes with totally unimodular faces
- Pseudodeterministic algorithms and the structure of probabilistic time
- Dynamic complexity of reachability: how many changes can we handle?
- Inductive tracing and the complexity of finding Hamiltonian path in DAGs
- If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n
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)
