4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You should put a bounty on this question. This way people are more likely to answer. Very interesting question by the way. $\endgroup$ – Boby Sep 5 '14 at 2:31
0
$\begingroup$

Information theory has been used to show lower bounds in communication complexity. This workshop at STOC '13 has talks going over the basics of the theory and some applications.

The description of Amit Chakrabarti's talk "Applications of information complexity I" mentions the use of information complexity in answering lower bound questions:

Information complexity was invented as a technique to prove a very specific direct sum result in communication complexity. Over the next decade, the notion of information complexity has been generalized, extended, and refined, leading to the rich theory we see today. I shall survey the key stages of this development, focusing on concrete lower bound questions that spurred it: both inside communication complexity and from applications in data streams and data structures.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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