# Entropy and computational complexity

There are researcher showing that erasing bit has to consume energy, now is there any research done on the average consumption of energy of algorithm with computational complexity $F(n)$? I guess, computational complexity $F(n)$ is correlated to the average consumption of energy, hope I can get some answer here.

• Linking to the paper in question would improve this question. – Stella Biderman Feb 4 '18 at 8:25
• @StellaBiderman thank you, but I have found no link in your comment. – XL _At_Here_There Feb 4 '18 at 8:37
• I don’t know what paper/researcher you’re talking about. I’m suggesting that you provide I – Stella Biderman Feb 4 '18 at 14:39
• @StellaBiderman I misunderstood your comments, actually I just read a text realating "erasing bit has to consume energy" in Kolmogorov complexity and its application by Viatanyi and Li. I think I have not read any other relating articles and books – XL _At_Here_There Feb 5 '18 at 3:29

Yes, but most of the work so far (except very recently, see below) has focused on turning irreversible computations into reversible ones, thereby hoping to avoid any entropy generation. (Note: there is an important difference between energy needed to make a computation run, and entropy generated by the computation and put out into the environment, typically in the form of heat.)

Based on Landauer and Bennett's original analysis that erasing a bit "must" generate $kT \ln(2)$ entropy (see below for why there are scare-quotes), several researchers have pursued various questions along these lines. One line of research was to simulate irreversible Turing machines by reversible ones, which, it was suggested, would generate no entropy. There are several works showing space-time tradeoffs for how to simulate irreversible TMs by reversible ones, e.g.:

More recently,

Demaine, Lynch, Mirano, and Tyagi. Energy-Efficient Algorithms, 2016.

studied partially reversible algorithms - that is, if you are willing to pay some entropy, for standard algorithmic tasks can one improve upon the general irreversible-to-reversible simulations mentioned above. Reversible computing has a whole community of researchers devoted to it, viz. the Reversible Computing conference, now in its 10th year.

It has actually been known for a long time, going all the way back to Landauer and Bennett, that the relationship between computational irreversibility and entropy generation is more subtle than is suggested by the tagline "erasing a bit generates $\ln(2)$ entropy." However, in the past 20 years or so nonequilibrium statistical mechanics has advanced to the point that this more subtle relationship can be captured by precise numerical equations involving not just entropy difference, but also a difference of KL divergences, see

Kolchinsky & Wolpert, Dependence of dissipation on the initial distribution over states. J. Stat. Mech. 2017 (arXiv link)

(and references therein).

We hosted a workshop on this at the Santa Fe Institute in August 2017 (where you can see the names of some researchers and talk titles of relevance), and it raises a whole new set of questions in both physics and thermodynamic computational complexity.

• Turing Machine or Church-Turing Thesis may be ruled or restricted by physical law, so the possibility whether quantum computation or quantum communication can be implemented may be deduced from physics law, like the second law of statistical mechanics, general relativity. So I guess if there is any result about the linkage of the thesis and physics law – XL _At_Here_There Feb 3 '18 at 2:56
• And it seems that physics site is not interested in the topics of this kind. – XL _At_Here_There Feb 3 '18 at 3:48
• @XL_at_China: There is a "Physical Church-Turing thesis", but this has little to do with the second law, since both the Church-Turing thesis and its physical version are just about what is computable, not about any kind of quantitative estimates, but the second law is a quantitative statement. Also, while there may not have yet been a ton of publications on it, at our workshop the physicists definitely seemed interested. – Joshua Grochow Feb 3 '18 at 6:39
• I had tried to find the linkage several years ago, but failed to get any result. Intuitively, the computability seems to have to be linked to the second thermodynamic law. And considering Turing Machine in the term of general relativity, the problem becomes interesting. But I do not know any physicists are interested in such a problem. – XL _At_Here_There Feb 3 '18 at 9:06
• And could we post a related question on physics of the site, and discuss it with physicist? – XL _At_Here_There Feb 3 '18 at 13:17