Determinism versus nondeterminism for linear time RAMs with memory restrictions
DOI10.1006/JCSS.2002.1821zbMATH Open1020.68035OpenAlexW1991155917MaRDI QIDQ1869934FDOQ1869934
Authors: 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
Recommendations
- Determinism versus non-determinism for linear time RAMs (extended abstract)
- Invariance properties of RAMs and linear time
- Trading determinism for time in space bounded computations
- scientific article; zbMATH DE number 2068877
- Lower Bounds for the Complexity of Functions in a Realistic RAM Model
- Deterministic versus nondeterministic time and lower bound problems
- scientific article; zbMATH DE number 1543044
- scientific article; zbMATH DE number 1998328
- scientific article; zbMATH DE number 1304315
- Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- A general Sequential Time-Space Tradeoff for Finding Unique Elements
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- A time-space tradeoff for sorting on non-oblivious machines
- Two time-space tradeoffs for element distinctness
- A Time-Space Tradeoff for Element Distinctness
- Near-Optimal Time-Space Tradeoff for Element Distinctness
Cited In (10)
- Finding the Median (Obliviously) with Bounded Space
- A nondeterministic space-time tradeoff for linear codes
- A note on the decoding complexity of error-correcting codes
- Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
- Quantum branching programs and space-bounded nonuniform quantum complexity
- Invariance properties of RAMs and linear time
- Determinism versus non-determinism for linear time RAMs (extended abstract)
- Choice-memory tradeoff in allocations
- Time-space tradeoffs for branching programs
- Limitations of incremental dynamic programming
This page was built for publication: Determinism versus nondeterminism for linear time RAMs with memory restrictions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1869934)
