TOPICS
Search

Rabin's Compression Theorem


For any constructible function f, there exists a function P_f such that for all functions t, the following two statements are equivalent:

1. There exists an algorithm A such that for all inputs x, A(x) computes P_f(x) in volume t(x).

2. t is constructible and f(x)=O(t(x)).

Here, the volume V_(A(x)) is the combined number of active edges during all steps, which is the number of state-changes needed to run a certain Turing machine on a particular input.


See also

Constructible Function

Explore with Wolfram|Alpha

References

Rabin, M. O. "Speed of Computation of Functions and Classification of Recursive Sets." Third Convention of Sci. Soc. Israel, pp. 1-2, 1959. Bull. Res. Council Israel 8F, 69-70, 1959.

Referenced on Wolfram|Alpha

Rabin's Compression Theorem

Cite this as:

Weisstein, Eric W. "Rabin's Compression Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RabinsCompressionTheorem.html

Subject classifications