most recent 30 from http://mathoverflow.net 2013-05-24T17:01:45Z http://mathoverflow.net/feeds/question/52590 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52590/abstract-notion-for-energy-complexity-of-computational-problems Mohammad Al-Turkistany 2011-01-20T07:31:53Z 2011-03-03T03:50:04Z

<p>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.</p> <blockquote> <p>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?</p> </blockquote> <p>This is a follow-up to this question on <a href="http://cstheory.stackexchange.com/questions/4204/formal-notion-for-energy-complexity-of-computational-problems" rel="nofollow">SE TCS</a> <a href="http://cstheory.stackexchange.com/questions/4204/formal-notion-for-energy-complexity-of-computational-problems" rel="nofollow"></a></p>

http://mathoverflow.net/questions/52590/abstract-notion-for-energy-complexity-of-computational-problems/52650#52650 David Harris 2011-01-20T16:45:50Z 2011-01-20T16:45:50Z

<p>The answer is no, energy cannot be considered a cost of computation.</p> <p>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.</p> <p>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.</p>

http://mathoverflow.net/questions/52590/abstract-notion-for-energy-complexity-of-computational-problems/57206#57206 none 2011-03-03T03:50:04Z 2011-03-03T03:50:04Z

<p>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:</p> <ul> <li><a href="http://cr.yp.to/nfscircuit/opcost.html" rel="nofollow">http://cr.yp.to/nfscircuit/opcost.html</a></li> <li><a href="http://cr.yp.to/papers/nfscircuit.pdf" rel="nofollow">http://cr.yp.to/papers/nfscircuit.pdf</a></li> <li><a href="http://cr.yp.to/snuffle/bruteforce-20050425.pdf" rel="nofollow">http://cr.yp.to/snuffle/bruteforce-20050425.pdf</a></li> </ul>