39
$\begingroup$

Computational complexity includes the study of time or space complexity of computational problems. From the the perspective of mobile computing, energy is very valuable computational resource. So, Is there a well studied adaptation of Turing machines that account for the energy consumed during the execution of algorithms. Also, Are there established energy-complexity classes for computational problems?

References are appreciated.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Energy consumption is machine dependent and a practical issue, i.e. the constants hidden in classical analysis are typically of interest (any the only difference between runtime and energy consumption). $\endgroup$
    – Raphael
    Commented Jan 9, 2011 at 19:26
  • 6
    $\begingroup$ Theoretically, you can do reversible steps with no energy cost. Practically, one can build chips which perform reversible steps at a substantially lower energy cost than non-reversible steps. How this translates into theory isn't clear, but maybe we can define a Turing machine model which does reversible steps at cost $\alpha$ and non-reversible steps at cost $\beta$, and start reasoning about energy consumption theoretically. At least it's possibly better than throwing up your hands in despair and saying "it's all machine dependent." $\endgroup$
    – Peter Shor
    Commented Jan 10, 2011 at 3:36
  • $\begingroup$ Possible related: How much computational power fits into a cubic centimeter?, DNA-algorithms and NP-completeness. $\endgroup$
    – Kaveh
    Commented Jan 10, 2011 at 3:50
  • $\begingroup$ Susanne Albers wrote an excellent survey in the Communication of ACM, Energy efficient algorithms. cacm.acm.org/magazines/2010/5/87271-energy-efficient-algorithms/… $\endgroup$
    – Mohammad Al-Turkistany
    Commented Sep 18, 2011 at 19:04
  • $\begingroup$ There is also this recent paper: doi.org/10.1103/PhysRevResearch.2.033312 Do you have any update in these past 10 years? $\endgroup$
    – domotorp
    Commented Nov 17, 2021 at 20:34

8 Answers 8

Reset to default
27
$\begingroup$

Is there a well studied adaptation of Turing machines that account for the energy consumed during the execution of algorithms? No!

But maybe you could come up with one. It's possible you could divide the Turing machine steps into reversible and non-reversible (the non-reversible ones are where information is lost). Theoretically, it is only the non-reversible steps that cost energy. A cost of one unit of energy for each bit that is erased would theoretically be the right measure.

There is a theorem of Charles Bennett that the time complexity increases by at most a constant when a computation is made reversible (C.H. Bennett, Logical Reversibility of Computation), but if there are also limits on space, then making the computational reversible might incur a substantial increase in time (Reference here). Landauer's principle says that erasing a bit costs $kT\, \ln 2$ of energy, where $T$ is temperature and $k$ is Boltzmann's constant. In real life, you cannot come anywhere close to achieving this minimum. However, you can build chips which perform reversible steps using substantially less energy than they use for irreversible steps. If you give reversible steps a cost of $\alpha$ and irreversible steps a cost of $\beta$, this seems like it may give a reasonable theoretical model.

I don't know how Turing machines with some reversible steps relate to chips with some reversible circuitry, but I think both models are worth investigating.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Peter, in discussions about Efficient Church-Turing Thesis, I remember reading about taking the amount of energy used in the computation into account. Do you know if there is a good reference on the topic? (I can post this as a separate question if you prefer that.) $\endgroup$
    – Kaveh
    Commented Jan 10, 2011 at 3:55
  • 4
    $\begingroup$ If you're just worried about polynomial factors, as you are for the Efficient Church-Turing thesis, everything works out, because you can get reversible computation (arbitrarily small amount of energy expended) with only a constant factor increase in time, and the space cannot be any larger than the time. I think I saw a good recent survey about this stuff. Hopefully somebody can locate it. $\endgroup$
    – Peter Shor
    Commented Jan 10, 2011 at 4:13
  • $\begingroup$ Thanks Peter, I guess I might find it myself using Google (I will post a question if I don't find). $\endgroup$
    – Kaveh
    Commented Jan 10, 2011 at 22:56
  • $\begingroup$ interesting ideas that lead to the question, how much can arbitrary algorithms be transformed into reversible computations? as in qm computing this is always possible with "ancilla" bits but keeping this "scratch" can decrease the efficiency of the algorithm in some cases and its maybe so far not so well understood how much. note williams has some ideas on space-efficient reversible computations $\endgroup$
    – vzn
    Commented Mar 3, 2013 at 2:11
  • $\begingroup$ Even if we have a reversible-computation machine, there are still some "hidden" energy costs: When we want to run a new computation, we must either build a new memory bank, or erase some of the previously-written data to make room for the new input and computations. How does this affect the answer? (e.g. does reversible computation usually assume access to a section of initialized, "blank" memory? seems like cheating...) $\endgroup$
    – usul
    Commented May 28, 2017 at 16:51
8
$\begingroup$

There aren't energy complexity classes yet, but there there's definitely a lot of interest in studying how to design algorithms that are energy efficient under some model. I'm not familiar with the entire body of work, but one entry point is the work that Kirk Pruhs is doing on sustainable computing. Kirk is a theoretician with expertise in scheduling and approximations, and has recently become very active in this area, so his perspective is a good one for algorithmic folks.

p.s gabgoh's point about Landauer's principle is a good one. If you want to learn more about the relation between energy and information, there's no better source than the Maxwell's Demon book.

Improve this answer
$\endgroup$
0
5
$\begingroup$

This isn't a direct answer at all, but are some potentially useful connections to draw/research programmes to be conducted along the lines of Stay and Baez' work on algorithmic thermodynamics: http://johncarlosbaez.wordpress.com/2010/10/12/algorithmic-thermodynamics/

Do take note, however, that this work does not draw out actual physical consequences -- rather it illustrates a connection that is, thus far, purely mathematical.

Improve this answer
$\endgroup$
5
$\begingroup$

Kei Uchizawa and his coauthors study the energy complexity of threshold circuits. They define it as the maximum number of threshold gates that output 1 over all possible inputs.

Since it's not about Turing machines, this doesn't answer the question. But, I hope their papers give some ideas. His webpage contains pointers. http://www.nishizeki.ecei.tohoku.ac.jp/nszk/uchizawa/

Improve this answer
$\endgroup$
4
$\begingroup$

There is some justification for using the external memory model as a model of energy-aware computation. Paolo Ferragina discussed this briefly in his invited talk at ESA 2010, but I don't know if there are any published results. The basic idea is that if the number of I/Os dominates computation time, then the energy required for those I/Os will probably dominate total energy consumption.

The report of the First Workshop on the Science of Power Management mainly contained questions and open problems. I don't know what happened at the Second Workshop, but the web pages tell that there will be a special issue of Sustainable Computing dedicated to theoretical, mathematical, and algorithmic approaches to sustainable computing.

Improve this answer
$\endgroup$
0
0
$\begingroup$

here are some newer/other references/angles on this apparently deep question with ongoing research. as indicated by P.Shor the area so far seems to be waiting on a comprehensive survey, standardization, and and/or unification. there are more abstract/theoretical approaches listed 1st, followed by more applied approaches: energy efficient algorithms, measurement of energy use in mobile for sorting, study of factors in VLSI affecting energy/time complexity.

Improve this answer
$\endgroup$
0
$\begingroup$

Recent result from Thermodynamics, actually Stochastic Thermodynamics, that relates the thermodynamic cost of running a Turing Machine, and circuit computation. Authors Kolchinsky, and Wolpert - they approach the problem of computing thermodynamic cost of running a Turing Machine, and circuits- their technique extends to TMs. By linking Kolgomorov complexity of the input to the compressibility of output they obtain thermodynamic bounds for computation. The difficulty of computing thermodynamic cost (of running a Turing Machine, circuit computation) is clear. By using Stochastic Thermodynamics to achieve computing the cost they indicate a divergence from Shannon entropy to compressibility, in computing the thermodynamic cost.

Each run of their model Turing Machine has a "heat" associated with it. In their model the random bits in input generate more "heat" vs computable inputs - this makes it consistent with the physical Church Turing thesis. They use techniques from Kolmogorov Complexity, (their "heat" analogues) to link to their thermodynamic cost of running a Turing Machine. The stochastic thermodynamic cost functions devised in such a way give them Kolmogorov related results of computation.

Improve this answer
$\endgroup$
-3
$\begingroup$

Time and space complexities are device independent. I don't see a way to make energy-complexity device independent.

If $W$ is work done by a Turing machine to perform one basic step. Then energy complexity becomes number of steps times $W$. $W$ is highly machine dependent.

And, $O(W f(n)) = O(f(n))$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ i am down-voting this answer as I think it misses the point. I think there is some theoretical justification for putting a lower bound on the energy consumption of any algorithm based on Landauer's principle. I find the question very sensible. $\endgroup$
    – gabgoh
    Commented Jan 9, 2011 at 17:37
  • $\begingroup$ @gabgoh I fear any general lower bound would have to make uniformity assumptions that would defeat the purpose. @TheMachineCharmer In fact, real processors can have different orderings of commands by efficiency. Upvote, althoug your second paragraph confuses me. $\endgroup$
    – Raphael
    Commented Jan 9, 2011 at 19:23
  • 4
    $\begingroup$ Time and space are NOT device-independent in exactly the same way that energy is not device-independent. A single computational step on a 1970 IBM 360 takes a lot longer than a single computational step on my laptop. Theoretically, a reversible computational step should cost $\alpha$ units of energy while a non-reversible computational step should cost $\beta$ units of energy, where the actual values of $\alpha$ and $\beta$ are machine dependent. However, the number of $\alpha$ and $\beta$ steps depends only on the program. $\endgroup$
    – Peter Shor
    Commented Jan 10, 2011 at 2:13
  • 1
    $\begingroup$ @Konrad: gabgoh is referring to Rolf Landauer, not Lev Landau. $\endgroup$
    – Peter Shor
    Commented Jan 10, 2011 at 2:15
  • 1
    $\begingroup$ @Peter: thanks for the info. For the record though, I was talking about Edmund Landau, inventor of the big-O notation. I thought that was what gabgoh was referring to with “Landauer’s principle”. $\endgroup$
    – Konrad Rudolph
    Commented Jan 10, 2011 at 8:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.