Time/Space Trade-Offs for Reversible Computation
From MaRDI portal
Publication:3832041
DOI10.1137/0218053zbMath0676.68010MaRDI QIDQ3832041
Publication date: 1989
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/500470befb771a5cb10095103f50b4cda75ff008
68Q25: Analysis of algorithms and problem complexity
Related Items
Unnamed Item, ON THE WORD PROBLEM FOR TENSOR PRODUCTS AND AMALGAMS OF MONOIDS, Time and space complexity of reversible pebbling, Breaking the Sub-Exponential Barrier in Obfustopia, Every polynomial-time 1-degree collapses if and only if P = PSPACE, CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS, Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants, Reversible simulation of space-bounded computations, Notes on Landauer's principle, reversible computation, and Maxwell's demon, Fundamentals of reversible flowchart languages, Reversible computing and cellular automata -- a survey, One-way permutations, computational asymmetry and distortion., Quantum circuit oracles for abstract machine computations, Computability and complexity of ray tracing, Common knowledge and update in finite environments, Reductions and functors from problems to word problems, Reversible space equals deterministic space, Quantum search on structured problems, \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata, Quantum computing and quadratically signed weight enumerators, Quantum neural networks, Quantum one-way permutation over the finite field of two elements, Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3, Low-communication parallel quantum multi-target preimage search, The complexity of reversible cellular automata, Space-bounded quantum complexity, Efficient and exact quantum compression, Pebbling meets coloring: reversible pebble game on trees, When-and how-can a cellular automaton be rewritten as a lattice gas?, A common algebraic description for probabilistic and quantum computations, A Hierarchy of Fast Reversible Turing Machines, Real-Time Methods in Reversible Computation, Ricercar: A Language for Describing and Rewriting Reversible Circuits with Ancillae and Its Permutation Semantics, Reversibility in space-bounded computation, Reversible and Irreversible Computations of Deterministic Finite-State Devices, Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks, Efficient Turing-Universal Computation with DNA Polymers, Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms, Reversible Pebble Game on Trees
