dorsal/arxiv
View SchemaTime and Space Bounds for Reversible Simulation
| Authors | Harry Buhrman, J. Tromp, Paul Vitanyi |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0101133 |
| URL | https://arxiv.org/abs/quant-ph/0101133 |
| DOI | 10.1088/0305-4470/34/35/308 |
| Journal | Journal of Physics A: Mathematical and General, 34(2001), 6821--6830. |
Abstract
We prove a general upper bound on the tradeoff between time and space that suffices for the reversible simulation of irreversible computation. Previously, only simulations using exponential time or quadratic space were known. The tradeoff shows for the first time that we can simultaneously achieve subexponential time and subquadratic space. The boundary values are the exponential time with hardly any extra space required by the Lange-McKenzie-Tapp method and the ($\log 3$)th power time with square space required by the Bennett method. We also give the first general lower bound on the extra storage space required by general reversible simulation. This lower bound is optimal in that it is achieved by some reversible simulations.
{
"annotation_id": "58567559-ad96-4213-9ca9-df52940bc523",
"date_created": "2026-03-02T18:01:42.309000Z",
"date_modified": "2026-03-02T18:01:42.309000Z",
"file_hash": "ef1bcc0b9459213c6ecef83ec807b89f86f6c14800c90fe8658037af3dc9c67d",
"private": false,
"record": {
"abstract": "We prove a general upper bound on the tradeoff between time and space that\nsuffices for the reversible simulation of irreversible computation. Previously,\nonly simulations using exponential time or quadratic space were known.\n The tradeoff shows for the first time that we can simultaneously achieve\nsubexponential time and subquadratic space.\n The boundary values are the exponential time with hardly any extra space\nrequired by the Lange-McKenzie-Tapp method and the ($\\log 3$)th power time with\nsquare space required by the Bennett method. We also give the first general\nlower bound on the extra storage space required by general reversible\nsimulation. This lower bound is optimal in that it is achieved by some\nreversible simulations.",
"arxiv_id": "quant-ph/0101133",
"authors": [
"Harry Buhrman",
"J. Tromp",
"Paul Vitanyi"
],
"categories": [
"quant-ph",
"cs.CC",
"cs.DS"
],
"doi": "10.1088/0305-4470/34/35/308",
"journal_ref": "Journal of Physics A: Mathematical and General, 34(2001),\n 6821--6830.",
"title": "Time and Space Bounds for Reversible Simulation",
"url": "https://arxiv.org/abs/quant-ph/0101133"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "90dd89e8-e616-4100-aab0-aeb3998e5c94",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}