Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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). –  Raphael Jan 9 '11 at 19:26
6  
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." –  Peter Shor Jan 10 '11 at 3:36
    
    
Susanne Albers wrote an excellent survey in the Communication of ACM, Energy efficient algorithms. cacm.acm.org/magazines/2010/5/87271-energy-efficient-algorithms/… –  Mohammad Al-Turkistany Sep 18 '11 at 19:04
add comment

7 Answers

up vote 24 down vote accepted

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.

share|improve this answer
    
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.) –  Kaveh Jan 10 '11 at 3:55
4  
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. –  Peter Shor Jan 10 '11 at 4:13
    
Thanks Peter, I guess I might find it myself using Google (I will post a question if I don't find). –  Kaveh Jan 10 '11 at 22:56
    
Thanks Peter for this excellent answer. –  Mohammad Al-Turkistany Jan 20 '11 at 7:53
    
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 –  vzn Mar 3 '13 at 2:11
add comment

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.

share|improve this answer
    
+1 Thanks Suresh for your answer. –  Mohammad Al-Turkistany Jan 20 '11 at 7:56
add comment

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.

share|improve this answer
add comment

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/

share|improve this answer
add comment

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.

share|improve this answer
    
Thanks Jouni, interesting point. –  Mohammad Al-Turkistany Jan 10 '11 at 8:56
add comment

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.

share|improve this answer
add comment

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))$.

share|improve this answer
    
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. –  gabgoh Jan 9 '11 at 17:37
    
@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. –  Raphael Jan 9 '11 at 19:23
4  
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. –  Peter Shor Jan 10 '11 at 2:13
1  
@Konrad: gabgoh is referring to Rolf Landauer, not Lev Landau. –  Peter Shor Jan 10 '11 at 2:15
1  
@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”. –  Konrad Rudolph Jan 10 '11 at 8:12
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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