Relationship between message entropy and complexity of the best algorithm

Question

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?

Answer 1

I believe you are looking for algorithmic information theory. This defines the information contained in a string as proportional to the size of the smallest program that produces that string. The metric is called Kolmogorov (Колмогоров) complexity.

The problem with normal Shannon entropy, is that it is defined relative to your assumed model of the producer of the information stream. Shannon entropy really only deals with models that produce infinite and stationary random streams. When you know that the producer is deterministic then the Shannon entropy of the stream is 0 (even though you don't know the algorithm of the producer.) You can often model a deterministic stream as some kind of Markov process, but there will always be a Markov process with more states that models the deterministic stream and in which the entropy is smaller.