Hi all,
Please tell me what is informationtheoretic lower bound. what does it really means
Thank you
Hi all, Please tell me what is informationtheoretic lower bound. what does it really means Thank you 

closed as not a real question by Scott Morrison♦ Feb 11 '10 at 4:57It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question. 


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 noncomputable, then this shows that B is also noncomputable. 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. 


I suspect you are discussing the bounds given by Shannon's work on information theory and socalled 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 wellstand to be clearer in general.) 


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. 

