> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/39.-compression-complexity-p-np/39.3-space-time-bounded-compression.md).

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