Timeline for Simpler proof of Rabin's Compression Theorem?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 27, 2015 at 20:03 | vote | accept | user833970 | ||
| Dec 27, 2015 at 20:03 | comment | added | user833970 | I finally tracked down the original citation, it is only an abstract for the talk, and isn't very helpful. | |
| Oct 13, 2015 at 18:25 | comment | added | user833970 | 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. | |
| Oct 12, 2015 at 22:39 | comment | added | Pseudonym♦ | 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! | |
| Oct 12, 2015 at 22:28 | comment | added | Pseudonym♦ | 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. | |
| Oct 12, 2015 at 22:12 | comment | added | user833970 | 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. | |
| Oct 12, 2015 at 21:22 | history | answered | Yuval Filmus | CC BY-SA 3.0 |