Reversible simulation of space-bounded computations
From MaRDI portal
Publication:673645
DOI10.1016/0304-3975(95)80017-4zbMath0873.68061OpenAlexW2018044965MaRDI QIDQ673645
Christos H. Papadimitriou, Pierluigi Crescenzi
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(95)80017-4
Related Items
Reversible computation in term rewriting ⋮ Space-bounded quantum complexity ⋮ Reversibility of computations in graph-walking automata ⋮ Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants ⋮ Reversible space equals deterministic space
Cites Work
- Symmetric space-bounded computation
- On the complexity of the parity argument and other inefficient proofs of existence
- Relationships between nondeterministic and deterministic tape complexities
- A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
- Irreversibility and Heat Generation in the Computing Process
- Time/Space Trade-Offs for Reversible Computation
- On Relating Time and Space to Size and Depth
- Quantum complexity theory
- Logical Reversibility of Computation
