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$
.

## Space-Bounded Compression

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.

## Space-Time-Bounded Compression

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.

## Efficient Bounded Compression

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.