Beyond Number of Bit Erasures: New Complexity Questions Raisedby Recently discovered thermodynamic costs of computation
Beyond Number of Bit Erasures: New Complexity Questions Raisedby Recently discovered thermodynamic costs of computation
复制标题
超越位擦除次数：最近发现的计算热力学成本提出的新复杂性问题
DOI：
10.1145/3232679.3232689
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Wolpert, David H.
中科院分区：
文献类型：
--
作者：
Grochow, Joshua A.;Wolpert, David H.
非平衡统计力学的最新进展使人们对计算的热力学成本有了比Landauer更深入的理解，并在计算复杂性领域进行了广泛的研究。特别值得一提的是，兰道尔的工作引起了人们对计算中位擦除次数的关注，因为它与输入和输出之间的熵变化有关。然而，物理学的新进展已经被实验证实，这意味着我们现在可以计算额外的热力学成本，而不仅仅是输入和输出之间的熵变化。因此，我们现在明白，虽然逻辑上可逆的计算可以有一些热力学上的好处，但它远未结束。这篇文章的目的是强调由于考虑这些新的热力学成本而在计算复杂性方面提出的新的开放问题。除了导致对逻辑可逆性的好处的修订观点外，这些问题还涉及随机化算法、平均情况复杂性、纠错码的热力学成本以及噪声/不精确/近似计算。
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.
登录
查看更多内容
平均情况复杂度理论
DOI：
10.1145/73007.73027
发表时间：
1989
期刊：
[1989] Proceedings. Structure in Complexity Theory Fourth Annual Conference
影响因子：
--
作者：
S. Ben;B. Chor;Oded Goldreich;M. Luby
通讯作者：
M. Luby
DOI：
10.1137/0215020
发表时间：
1986-02
期刊：
SIAM J. Comput.
影响因子：
--
作者：
L. Levin
通讯作者：
L. Levin
可逆元胞自动机的复杂性
DOI：
10.1016/j.tcs.2004.06.011
发表时间：
2004
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Klaus Sutner
通讯作者：
Klaus Sutner
基体刚度
影响因子：
11.6
作者：
B. Codenotti
通讯作者：
B. Codenotti
影响因子：
2.4
作者：
Prokopenko, Mikhail;Einav, Itai
通讯作者：
Einav, Itai