|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Time and Space Bounds for Reversible Simulation | | Harry Buhrman
; J. Tromp
; Paul Vitanyi
; | | Date: |
29 Dec 2000 | | Journal: | Journal of Physics A: Mathematical and General, 34(2001), 6821--6830. | | Subject: | Quantum Physics; Computational Complexity; Data Structures and Algorithms | quant-ph cs.CC cs.DS | | Affiliation: | CWI and Univ. Amsterdam), J. Tromp (CWI and BioInformatics Solutions), Paul Vitanyi (CWI and Univ. Amsterdam | | 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. | | Source: | arXiv, quant-ph/0101133 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER