I was doing a presentation on Rabin's Compression Theorem, when someone in the audience brought up a point I have no answer to.

Rabin's Compression Theorem states that every reasonable complexity class has a problem that can be solved optimally in it. The proof is a little involved, but not horribly difficult.

The audience member proposed a much simpler proof. For the given complexity class, calculate the target volume of computation from the input length. Then write that many hashes to the output.

Does this really prove the same result?

Also, I have had a lot of trouble finding Rabin's original paper. Does anyone know how to get it?

A formal version of the argument would be: Given a constructible function $f$, find a program that is optimal for $O(f(x))$ time, where $x$ is the length of the input.

def program(input):
    x = len(input)          # takes O(x) to read input of length x
    target = f(x)           # f is constructable, computing f(x) takes at most O(f(x))
    for _ in range(target): # takes exactly O(f(x)) to loop f(x) times
        print('1')          # assume we can append to the output in O(1)

The runtime of the algorithm is clearly $O(f(x))$.

The algorithm is optimal: Any program that prints $f(x)$ "1"s requires at least $f(x)$ steps.

As far as I can tell, this proof seems to work. It almost certainly proves something similar. However, I can't understand why the original proof would be so complicated, if this simpler proof works. This makes me worry that maybe I misunderstood something: e.g., about why the original statement is important/interesting, or about whether this simpler proof is correct and proves what it needs to prove. Can anyone help clear this up for me?

  • 1
    $\begingroup$ Isn't Rabin's theorem about decidable sets? The output of a decision procedure is one bit of information... $\endgroup$ – Pseudonym Oct 9 '15 at 3:02
  • 2
    $\begingroup$ Since you have already done the work, please expand the idea into a more detailed sketch of the proof. For instance, I have no idea what you mean by "target volume" and how to compute it from the input length. $\endgroup$ – Raphael Oct 9 '15 at 5:56
  • $\begingroup$ I suggest you formally try to prove the theorem using the function you suggest, and see whether it works or not. I bet that it won't. Try to use the formal definitions of all the relevant concepts. $\endgroup$ – Yuval Filmus Oct 12 '15 at 21:07

It is hard to answer this question since it is hard to find a formal statement of Rabin's compression theorem. Here is one from the book Complexity Theory and Cryptology: An Introduction to Cryptocomplexity by Jörg Rothe, page 63:

For each time constructible function $t(n)$ there exists a decidable set $D_t$ such that each deterministic Turing machine $M$ deciding $D_t$ must run in time larger than $t(n)$ for all large enough $n$.

Granted, this is not exactly your statement (it might be a different theorem proven in the same technical report of Rabin from 1960, or perhaps a different publication of Rabin from the same year), and it also differs from the rather unclear statement in Levin's lecture notes, which is closer to your statement but also seems to mention a predicate (though Levin's proof doesn't result in a predicate).

Both statements are somewhat different than your informal statement that every complexity class has a problem that can be solved optimally in it. They also seem to mention that the problem can be chosen to be a predicate.

In order to make progress, I suggest that you update your question with a complete formal statement of Rabin's compression theorem as you understand it, explaining no longer standard notions such as volume. Then try to formally prove the theorem along the lines you mention. If you succeed, include the proof. If you fail, you have answered your own question.

It is likely that there is some easy version of the theorem that does follow from your argument, but the actual theorem is harder, requiring either a delicate priority argument (like in the book) or a Kolmogorov complexity argument (like in Levin's notes). This may be due to one of two features of Rabin's theorem:

  1. It gives a predicate rather than an arbitrary function.

  2. The actual guarantee is a bit different. For example, in Levin's version you should be able to compute the function in all volumes which are asymptotically larger than the optimal complexity.

Also, depending on your computation model, your own function might not be computable in your own time bound (though multitape machines seem fine here).

Why am I so sure that there is something wrong with your argument? Your argument is very simple, and I find it hard that it was missed by both Rabin and Levin. It is much more probable that it just doesn't work, or that it proves a weaker version of the theorem.

  • $\begingroup$ Thanks, I'll take a look at that other formulation. I'm also pretty sure there's a problem with the argument, it just wasn't obvious to me what was wrong. $\endgroup$ – user833970 Oct 12 '15 at 22:12
  • $\begingroup$ Yes, I agree. A large number of people who have studied computational complexity have noticed at some point that it's trivial to concoct a problem where the size of the output is $O(f(n))$ for any $f(n)$. That's one of the reasons why decision problems are ubiquitous in this field; when the size of the output is $O(1)$, writing the output doesn't contribute. Be clear on the precise statement of the theorem, and it should be obvious why the trivial "proof" doesn't prove it. $\endgroup$ – Pseudonym Oct 12 '15 at 22:28
  • 1
    $\begingroup$ Oh, one more thing: as previously noted, "you can construct a predicate from any program". That's true, but never forget that complexity is measured in terms of the size of the input. In this case, input to the program is presumably a fixed sequence of hashes. It's possible to recognise that in $O(n)$ time where $n$ is the length of the input; it's just a string comparison! $\endgroup$ – Pseudonym Oct 12 '15 at 22:39
  • $\begingroup$ I see, by defining the input in terms of a predicate you effectively bound the size of the output. The mathworld link is misleading then for not bounding the output, or declaring a predicate. $\endgroup$ – user833970 Oct 13 '15 at 18:25
  • $\begingroup$ I finally tracked down the original citation, it is only an abstract for the talk, and isn't very helpful. $\endgroup$ – user833970 Dec 27 '15 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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