What is information-theoretic lower bound? [closed]

Question

Hi all,

Please tell me what is information-theoretic lower bound. what does it really means

Thank you

Answer 1

Without more context for your question, it is impossible to say, but one interpretation is that you may simply be asking about Turing degrees. A set A of natural numbers is a lower bound for the computational complexity of another set B if the characteristic function of A is computable from B, meaning that a Turing machine with oracle B can compute A. If A is itself non-computable, then this shows that B is also non-computable. In practice, this is how many noncomputability results are proved: one has a set B, and proves that it is undecidable by showing that the halting problem reduces to it.

The hierarchy of Turing degrees can be thought of as informational theoretic in nature. If A reduces to B, then B has at least as much information as A.

But you may have a more engineering purpose in mind, or an idea more connected directly with the issues in information theory, in which case this answer is not what you want.

Answer 2

A lower bound (usually crude but relatively easy to prove) on the amount of resources needed to solve a problem, based on the number of bits of information needed to uniquely specify the answer or some other structure related to the problem.

Example 1. Sorting a list using comparisons (is element at position P larger than the element at position Q) takes at least log_2(n!) operations because there are n! possible unsorted orderings.

Example 2. With probability approaching 1, a random (large, finite) graph has no automorphisms. This is because a graph with a nontrivial symmetry can be encoded in less space than writing down one bit per edge. OK, this is is an "information theoretic argument" rather than a lower bound on a computational problem, but the idea is the same.

Notice that example 2 fails for trees, which do generically have automorphisms. This can be seen because the number of bits of information to encode a tree is about log(n^n) = nlog(n), and while there would be a savings of data from having an automorphism, the additional number of bits needed to specify the automorphism is itself of order nlog(n) and the argument breaks down.

Answer 3

I suspect you are discussing the bounds given by Shannon's work on information theory and so-called Shannon entropy (e.g., the bounds given by the Shannon coding theorem). However, I think you need to be more specific about the context you are looking at before anyone can give a good response to "what does it really means". (Indeed, I think your question could well-stand to be clearer in general.)