Pergunta

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?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top