Determinism versus nondeterminism for linear time RAMs with memory restrictions

DOI10.1006/jcss.2002.1821zbMath1020.68035OpenAlexW1991155917MaRDI QIDQ1869934

Miklós Ajtai

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

zbMATH Keywords

computational modelrandom access machine

Mathematics Subject Classification ID

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