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
ON THE WORD PROBLEM FOR TENSOR PRODUCTS AND AMALGAMS OF MONOIDS, Time and space complexity of reversible pebbling, 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, 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, The complexity of reversible cellular automata, Space-bounded quantum complexity, Efficient and exact quantum compression, When-and how-can a cellular automaton be rewritten as a lattice gas?, A common algebraic description for probabilistic and quantum computations, Efficient Turing-Universal Computation with DNA Polymers
