__
TR11-069 | 18th April 2011 16:43
__

#### On the optimal compression of sets in PSPACE

**Abstract:**
We show that if DTIME[2^{O(n)}] is not included in DSPACE}[2^{o(n)}], then, for every set B in PSPACE, all strings x in B of length n can be represented by a string compressed(x) of length at most log (|B^{=n}|) + O(log n), such that a polynomial-time algorithm, given compressed(x), can distinguish x from all the other strings in B^{=n}.

Modulo the O(log n) additive trem, this achieves the information-theoretical optimum for string compression.