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
.
However, what about the problem of space-bounded compression? In this problem, we take in two inputs: a bitstream
and a target size
. The goal, then, is to find a program of length
that outputs
.
It turns out that such a problem is also uncomputable. If it were, then we could simply binary search on different values of
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
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
, and in the end, it will either output some program
P that has the correct output and is bounded by and
, or return that no such program is possible.
The runtime above is exponential in
. 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