A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
From MaRDI portal
Publication:3474887
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
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
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
