Complexity vs Energy: Theory of Computation and Theoretical Physics
arXiv:1302.6695 · doi:10.1088/1742-6596/532/1/012018
Abstract
This paper is a survey dedicated to the analogy between the notions of {\it complexity} in theoretical computer science and {\it energy} in physics. This analogy is not metaphorical: I describe three precise mathematical contexts, suggested recently, in which mathematics related to (un)computability is inspired by and to a degree reproduces formalisms of statistical physics and quantum field theory.
arXiv comment23 pages. Talk at the satellite conference to ECM 2012, "QQQ Algebra, Geometry, Information", Tallinn, July 9-12, 2012
References in corpus (9)
- Renormalization in quantum field theory and the Riemann-Hilbert problem I: the Hopf algebra structure of graphs and the main theorem
- Zipf's Law and Avoidance of Excessive Synonymy
- Universality of Zipf's Law
- Classical computing, quantum computing, and Shor's factoring algorithm
- Renormalization and computation I: motivation and background
- Software Libraries and Their Reuse: Entropy, Kolmogorov Complexity, and Zipf's Law
- A computability challenge: asymptotic bounds and isolated error-correcting codes
- Renormalization and Computation II: Time Cut-off and the Halting Problem
- Zipf's law and L. Levin's probability distributions