39.3 Space/Time-Bounded Compression

As described in the previous chapter, it is impossible to write the "perfect" compression algorithm that requires the fewest bits to output some bitstream BB.

Space-Bounded Compression

However, what about the problem of space-bounded compression? In this problem, we take in two inputs: a bitstream BB and a target size SS. The goal, then, is to find a program of length S\leq S that outputs BB.

It turns out that such a problem is also uncomputable. If it were, then we could simply binary search on different values of SS to find the optimal compression program size, which is impossible as shown in te previous section.

Space-Time-Bounded Compression

What if we take our problem from above, and add a constraint that we can run at most TT lines of bytecode?

It might seem unintuitive, but this kind of problem is actually solvable. We will use the following algorithm:

for length L = 1....S:
    for each possible program P of length L:
        while (P is running && !(B is outputted) && lines_executed < T):
            run the next line of P

The runtime of this algorithm is O(T2S)O(T * 2^S), and in the end, it will either output some program P that has the correct output and is bounded by TT and SS, or return that no such program is possible.

Efficient Bounded Compression

The runtime above is exponential in SS. Thus, we might ask if it's possible to solve the space-time-bounded compression problem efficiently. As we'll see in the next chapter, this depends on our definition of efficiency.

Last updated