Physical portrayal of computational complexity

DOI10.5402/2012/321372zbMath1235.68073WikidataQ58690811 ScholiaQ58690811MaRDI QIDQ408483

Arto Annila

Publication date: 10 April 2012

Published in: ISRN Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.5402/2012/321372

Mathematics Subject Classification ID

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Natural games

Uses Software

• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• A Mathematical Theory of Communication
• Physical foundations of evolutionary theory
• Notes on Landauer's principle, reversible computation, and Maxwell's demon
• Clifford algebra to geometric calculus. A unified language for mathematics and physics
• What does it mean to say that a physical system implements a computation?
• Complexity of protein folding
• From Kuramoto to Crawford: Exploring the onset of synchronization in population of coupled oscillators
• Natural games
• The physical nature of information
• Natural distribution
• Minimal Energy Requirements in Communication
• Information Theory and Statistical Mechanics
• Probability, ergodicity, irreversibility and dynamical systems
• In the light of time
• The physical character of information
• Irreversibility and Heat Generation in the Computing Process
• Invariant variation problems
• On the Structure of Polynomial Time Reducibility
• Information theory explanation of the fluctuation theorem, maximum entropy production and self-organized criticality in non-equilibrium stationary states
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• Physics and Computation: The Status of Landauer’s Principle
• Natural selection for least action
• The complexity of theorem-proving procedures
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Natural proofs