Beyond Number of Bit Erasures
| Autor: | David H. Wolpert, Joshua A. Grochow |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Nonequilibrium statistical mechanics
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Multidisciplinary Theoretical computer science Computational complexity theory Entropy (statistical thermodynamics) Computation 0102 computer and information sciences 01 natural sciences Randomized algorithm 010201 computation theory & mathematics 0103 physical sciences Error correcting Reversible computing 010306 general physics |
| Zdroj: | ACM SIGACT News. 49:33-56 |
| ISSN: | 0163-5700 |
| Popis: | Recent advances in nonequilibrium statistical mechanics have led to a deeper understanding of the thermodynamic cost of computation than that put forth by Landauer and then studied extensively in the computational complexity community. In particular, Landauer's work led to a focus on the number of bit erasures in a computation, due to its relation to the change in entropy between input and output. However new advances in physics|which have been experimentally con rmed|mean we can now calculate additional thermodynamic costs beyond merely the change in entropy between input and output. As a consequence, we now understand that while logically reversible computing can have some thermodynamic bene ts, it is far from the end of the story. The purpose of this paper is to highlight new open questions in computational complexity raised by consideration of these new thermodynamic costs. Beyond leading to a revised viewpoint on the bene ts of logical reversibility, these questions touch on randomized algorithms, average-case complexity, the thermodynamic cost of error correcting codes, and noisy/inexact/approximate computation. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|