19
$\begingroup$

You have an array of $n$ distinct elements. You have access to a comparator (a black box function taking two elements $a$ and $b$ and returning true iff $a < b$) and a truly random source of bits (a black box function taking no arguments and returning an independently uniformly random bit). Consider the following two tasks:

  1. The array is currently sorted. Produce a uniformly (or approximately uniformly) randomly selected permutation.
  2. The array consists of some permutation selected uniformly at random by nature. Produce a sorted array.

My question is

Which task requires more energy asymptotically?

I am unable to define the question more precisely because I don't know enough about the connection between information theory, thermodynamics, or whatever else is needed to answer this question. However, I think the question can be made well-defined (and am hoping someone helps me with this in an answer!).

Now, algorithmically, my intuition is that they are equal. Notice that every sort is a shuffle in reverse, and vice versa. Sorting requires $\log n! \approx n \log n$ comparisons, while shuffling, since it picks a random permutation from $n!$ choices, requires $\log n! \approx n \log n$ random bits. Both shuffling and sorting require about $n$ swaps.

However, I feel like there should be an answer applying Landauer's principle, which says that it requires energy to "erase" a bit. Intuitively, I think this means that sorting the array is more difficult, because it requires "erasing" $n \log n$ bits of information, going from a low-energy, high-entropy ground state of disorder to a highly ordered one. But on the other hand, for any given computation, sorting just transforms one permutation to another one. Since I'm a complete non-expert here, I was hoping someone with a knowledge of the connection to physics could help "sort" this out!

(The question didn't get any answers on math.se, so I'm reposting it here. Hope that is ok.)

Improve this question
$\endgroup$
15
  • $\begingroup$ I haven't thought this through at all, so caveat lector. If we start with a sorted array, then use merge sort, but instead of comparing, we use the random bits to do the merging (so instead of returning true iff $a<b$ we return true iff the random bit is $1$). The base case where we have two arrays of size one produces the two possible arrays of size two with a uniform probability. I haven't gotten any further than that. $\endgroup$
    – Luke Mathieson
    Apr 14, 2013 at 5:20
  • 2
    $\begingroup$ I think that in order to answer this question, you first need to define the relative costs of operation; how much does it cost to read data, write data, and generate/obtain a random number? $\endgroup$
    – mitchus
    Apr 14, 2013 at 7:49
  • $\begingroup$ @mitchus: I am mainly curious about the physical limits if we assume "optimally efficient" computers. My rough understanding is that there is a physical lower bound on the amount of energy required to "erase" a bit of information, while other operations require much less energy. So I wonder if this intuition is correct and formalizable enough to yield an answer. $\endgroup$
    – usul
    Apr 14, 2013 at 7:57
  • $\begingroup$ What do you mean by erasing a bit? Overwriting it? As far as I know computers don't usually erase anything (except for privacy reasons) but merely "forget" about it by de-allocating the associated memory region. But maybe I am not grasping the abstraction level correctly here :) $\endgroup$
    – mitchus
    Apr 14, 2013 at 8:17
  • 2
    $\begingroup$ @Patrick87 Unfortunately, a uniform energy model is too far from the truth to use it; see Evaluating Algorithms according to their Energy Consumption by Fudeus née Bayer and Nebel (2009). $\endgroup$
    – Raphael ♦
    Apr 14, 2013 at 16:07

2 Answers 2

Reset to default
6
$\begingroup$

By Landauer's principle, if you want to take a uniform random permutation of $n$ keys to a sorted one, and not keep any bits in the computer which reveal what the uniform random permutation was, you need to erase $log n! \approx n \log_2 n$ bits. This will take $(n \ln n) k T$ energy. On the other hand, the computation taking the sorted array and $n \log_2 n$ random bits to the random array is reversible, and thus the energy expended can be made arbitrarily small.

Note that these are just theoretical lower bounds. The energy currently consumed by these processes on an actual digital computer bears no relation to the above analysis.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks very much! Can I ask a possibly naive follow up? Suppose I change the wording of the question so that the sorting algorithm is given some fixed permutation of the items and must sort them. Now, if you subscribe to a Bayesian philosophy and have a uniform belief on this input, it seems the answer should be the same. But under a philosophy that there is no randomness in the input (although I don't know what it is), the argument seems to fail. How do I resolve the paradox? Thanks again!! $\endgroup$
    – usul
    Apr 24, 2013 at 16:26
  • $\begingroup$ @usul: in that case,you've still erased the bits, so the algorithm still takes $(n \ln n) kT$ energy. It's just that in this case, there is a better algorithm you could have used, if you had known which fixed permutation the input was. $\endgroup$
    – Peter Shor
    Apr 24, 2013 at 16:29
3
$\begingroup$

Neither. Any circuit can be made reversible by keeping track of the input, and the energy dissipation of reversible computation can be made arbitrarily small.

Improve this answer
$\endgroup$
3
  • $\begingroup$ but making it reversible might make it non-efficient. What is the relation between the optimal algorithms. BTW, i don't think they compare. Shuffling inherently requires randomness (and any different randomness will produce a different output). Sorting may be deterministic. "Reversing" sorting will shuffle in a deterministic way. $\endgroup$
    – Ran G.
    Apr 19, 2013 at 6:01
  • 1
    $\begingroup$ By "efficient" do you mean time, space, or some combination of the two? Making a computation reversible doesn't necessarily add asymptotic time complexity, and there exist reversible versions of every computation that use no more space than the original [Vitányi05]. $\endgroup$
    – rphv
    Apr 20, 2013 at 1:16
  • 1
    $\begingroup$ As long as you keep the input around, any circuit can be made reversible. If you don't want to keep information that can reconstruct the original permutation around, the sorting circuit cannot be made reversible. $\endgroup$
    – Peter Shor
    Apr 21, 2013 at 12:10

Your Answer

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

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