3
$\begingroup$

Energy is very valuable computational resource especially in mobile computing. Optimizing the energy consumed during the execution of algorithms has significant practical implications. Intuitively, It seems that such abstract energy measure has to be correlated to the time complexity, the space complexity, and the frequency of space (memory) access operations. Communications costs should be accounted for if we consider distributed computing model.

Are there abstract notions of energy (possibly analogous to the action quantity in physics) which could be useful for establishing energy-complexity classes for computational problems?

This is a follow-up to this question on SE TCS

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

The answer is no, energy cannot be considered a cost of computation.

Classical computations can be transformed, with only polynomial size blow-up, to reversible computations (computations which do not have operations like AND, OR which lose information). Instead, operation like $x \rightarrow x + y z$ are used, which are involutions. This transformation may require writing to an auxiliary scratch space, also polynomial sized. Reversible computations, in principle, do not require energy.

You allude to practical considerations like mobile computing. I do not believe (but am not sure of this) that the intrinsic energy loss from information-destroying operations plays a significant role in the real-world energy losses of computational devices.

Improve this answer
$\endgroup$
1
  • 6
    $\begingroup$ There has been some research on making low-energy computer chips using ideas from reversible computation, where reversible steps take considerably less energy than irreversible steps (although neither came anywhere close to the $kT\,\ln 2$ of Landauer's principle). I don't know whether any companies are currently considering making low-energy chips based on reversibility, though. $\endgroup$
    – Peter Shor
    Commented Jan 21, 2011 at 2:09
2
$\begingroup$

Yes, DJ Bernstein has a big rant which shows up (for example) in his work on integer factorization circuits. He goes a bit further than "energy" and discusses assigning a cost in dollars to a computation (in terms of the hardware needed, etc). He uses this measure to evaluate various trade-offs in serial vs. parallel computation, and argues that lots of existing analyses use the wrong measures and for that reason reach the wrong conclusions even asymptotically. Some links:

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .