Determinism versus nondeterminism for linear time RAMs with memory restrictions

DOI10.1006/JCSS.2002.1821MaRDI QIDQ1869934zbMATHOpenAlexFDO

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

zbMATH Keywords

computational modelrandom access machine

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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

Cites work

• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 3481857 (Why is no real title available?)
• A Time-Space Tradeoff for Element Distinctness
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• A time-space tradeoff for sorting on non-oblivious machines
• Near-Optimal Time-Space Tradeoff for Element Distinctness
• Two time-space tradeoffs for element distinctness

Cited in

(10)

• Finding the Median (Obliviously) with Bounded Space
• Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
• Quantum branching programs and space-bounded nonuniform quantum complexity
• Determinism versus non-determinism for linear time RAMs (extended abstract)
• Choice-memory tradeoff in allocations
• A note on the decoding complexity of error-correcting codes
• Limitations of incremental dynamic programming
• Invariance properties of RAMs and linear time
• A nondeterministic space-time tradeoff for linear codes
• Time-space tradeoffs for branching programs

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)