A Note on Bennett’s Time-Space Tradeoff for Reversible Computation

DOI10.1137/0219046zbMath0697.68043OpenAlexW2022763264MaRDI QIDQ3474887

Alan T. Sherman, Robert Levine

Publication date: 1990

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/3c89dd1992b34aafd7122a400616c4f2a09cb85f

zbMATH Keywords

algorithmstime-space tradeoffreversible computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (17)

Low-gate quantum golden collision finding ⋮ Time and space complexity of reversible pebbling ⋮ Beyond quadratic speedups in quantum attacks on symmetric schemes ⋮ New results on \(\mathsf{Gimli}\): full-permutation distinguishers and improved collisions ⋮ On treewidth, separators and Yao's garbling ⋮ Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem ⋮ PSPACE-completeness of certain algorithmic problems on the subgroups of free groups ⋮ Reversible simulation of space-bounded computations ⋮ Quantum circuit oracles for abstract machine computations ⋮ Notes on Landauer's principle, reversible computation, and Maxwell's demon ⋮ Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Internal symmetries and linear properties: full-permutation distinguishers and improved collisions on \textsf{Gimli} ⋮ Real-Time Methods in Reversible Computation ⋮ Reversible space equals deterministic space ⋮ \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata ⋮ Quantum security analysis of CSIDH

This page was built for publication: A Note on Bennett’s Time-Space Tradeoff for Reversible Computation