-4
$\begingroup$

Hi all,

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

Thank you

$\endgroup$
3
  • $\begingroup$ i'm really sorry for not having more context in my question. I was actually referring to the cost of computing a data structure for example OBNR (Order by next request). $\endgroup$
    – jeremy
    Feb 11, 2010 at 3:22
  • 6
    $\begingroup$ You can edit your posts, and doing so is recommended. $\endgroup$
    – Ben Webster
    Feb 11, 2010 at 4:19
  • 5
    $\begingroup$ Closed. Sorry, but we expect a certain level of effort from people asking questions on mathoverflow. Providing sufficient context, especially when asked, is certainly one requirement. To be picky, questions marks are another. Feel free to edit and improve the question up to an appropriate standard, and then flag for moderator attention for reopening. You might look at the mathoverflow.net/howtoask page for ideas about how to write good questions. $\endgroup$ Feb 11, 2010 at 4:59

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.)

$\endgroup$

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