# Relationship between message entropy and complexity of the best algorithm

Is it possible to estimate number of steps in best possible algorithm for classification of messages, using entropy of messages?

E.g. linear search problem. We have an ordered set of incomparable elements (no < and >, equivalence only) of length $N$, and element for search – A, which could be in set maximum once. Set could be represented as sequence like 00001000, length $N$, where 1/0 means that element here equals A/not equals A. Algorithm parses the message and responds "not contains" (for one message 00000...0 ) and "contains" (all other messages). For uniform probability of being equal A for each position, entropy of responses equals: $$H=-\frac{1}{N+1}\cdot \log_2\left(\frac{1}{N+1}\right) - \frac{N }{N+1} \cdot \log_2\left(\frac{N}{N+1}\right)$$ $H$ goes to zero quickly:

We also know that $\lfloor\text{entropy}\rfloor+1$ equals the mean message length in case of best coding (Shannon's source coding theorem for symbol codes). That means we could index any message with binary string, and it will take us only one symbol – one step in algorithm!

But existing codes for linear search (e.g. brute force) require $\frac{N+1}{2}>1$ steps, and all improved techniques require comparability (e.g. binary search).

This suggests that entropy of message does not equal the number of step in best possible algorithm of problem solution (=message classification).

But then what is the link between both? Is there any relationship between the number of steps for the abstract "best code" and the entropy of message?

• What problem is an "algorithm for classification of messages" supposed to solve? $\hspace{1.54 in}$ – user12859 Aug 14 '14 at 18:32
• It has to answer "contains" or "does not contain", for given message (e.g. 0000 "does not contain", 0010 "contains"), it's just a linear search. – Евгения Карпова Aug 14 '14 at 18:49