Determinism versus nondeterminism for linear time RAMs with memory restrictions
From MaRDI portal
Publication:1869934
DOI10.1006/jcss.2002.1821zbMath1020.68035OpenAlexW1991155917MaRDI QIDQ1869934
Publication date: 4 May 2003
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/a3ac601e071565d41452ae63aff4a812f3cc1264
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (8)
Finding the Median (Obliviously) with Bounded Space ⋮ A note on the decoding complexity of error-correcting codes ⋮ Limitations of incremental dynamic programming ⋮ A nondeterministic space-time tradeoff for linear codes ⋮ Quantum branching programs and space-bounded nonuniform quantum complexity ⋮ Choice-memory tradeoff in allocations ⋮ Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle ⋮ Time-space tradeoffs for branching programs
Cites Work
- Unnamed Item
- Unnamed Item
- Two time-space tradeoffs for element distinctness
- A time-space tradeoff for sorting on non-oblivious machines
- A general Sequential Time-Space Tradeoff for Finding Unique Elements
- A Time-Space Tradeoff for Element Distinctness
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- Near-Optimal Time-Space Tradeoff for Element Distinctness
This page was built for publication: Determinism versus nondeterminism for linear time RAMs with memory restrictions
