Time and space bounds for reversible simulation
From MaRDI portal
Publication:2766195
DOI10.1088/0305-4470/34/35/308zbMath0988.81021arXivquant-ph/0101133OpenAlexW3101299045MaRDI QIDQ2766195
John Tromp, Paul M. B. Vitányi, Harry Buhrman
Publication date: 27 January 2002
Published in: Journal of Physics A: Mathematical and General (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/quant-ph/0101133
subexponential timeirreversible computationLange-McKenzie-Tapp methodsubquadratic spacetrade-off between time and space
Related Items
Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms ⋮ Reversibility of computations in graph-walking automata ⋮ Design of 1-tape 2-symbol reversible Turing machines based on reversible logic elements ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Ricercar: A Language for Describing and Rewriting Reversible Circuits with Ancillae and Its Permutation Semantics ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling
