Theoretical investigations on the energy requirements of computation under limited resources

Abstract

Computational complexity theory investigates the minimum amount of resources needed to perform a computation, and time and space complexity are the most popular of such measures. Landauer has shown that energy, just like time and space, is a resource, and quantified the amount of energy needed and when. We use Landauer's findings to naturally formulate the energy complexity of deterministic finite automata and machines with a single access to their input, and investigate it through the lens of computational complexity theory.