Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was just wondering whether or not information entropy has significant applications to complexity theory.

I ask because of a simple example I thought of. It comes from a riddle. Suppose you had 8 balls, one of which is slightly heavier than the rest but all of them look identical. You are tasked with determining the odd one out by using a scale, where you place any number of balls on each side. What is the least number of times you can use the scale?

At first you might think 3, by splitting the balls in half each time, but you can actually do it in 2, by splitting the balls into (approximately) thirds each time, weighing two of them (of equal size) and if they balance then you know that the ball remains in the unweighed group. So the question then becomes what is the minimum number of weighings required for $n$ balls instead?

If you have $n$ balls then the probability that the heavy ball is any one of them is equal so your current uncertaintiy is $H(1/n,\cdots,1/n) = \log n$ Since the scale can only do three things, fall left, fall right, or stay still, you can see that the maximum amount of entropy for a weighing is $H(1/3,1/3,1/3) = \log 3$. If you know which ball it is the entropy of the situation is 0. Each weighing decreases the total entropy by the entropy of that weighing. So, no matter what, you'll require at least $(\log n) / (\log 3) = \log_3 n$ weighings to discover the heavy ball.

I'm just curious whether or not methods like this are ever used to discover a lower bound to more complicated problems.

share|improve this question

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.