Comment on page

# 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

$B$

. However, what about the problem of space-bounded compression? In this problem, we take in two inputs: a bitstream

$B$

and a target size $S$

. The goal, then, is to find a program of length $\leq S$

that outputs $B$

. It turns out that such a problem is also uncomputable. If it were, then we could simply binary search on different values of

$S$

to find the optimal compression program size, which is impossible as shown in te previous section.What if we take our problem from above, and add a constraint that we can run at most

$T$

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(T * 2^S)$

, and in the end, it will either output some program `P`

that has the correct output and is bounded by $T$

and $S$

, or return that no such program is possible.The runtime above is exponential in

$S$

. 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 modified 7mo ago