Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-069 | 18th April 2011 16:43

On the optimal compression of sets in PSPACE

RSS-Feed




TR11-069
Authors: Marius Zimand
Publication: 29th April 2011 10:41
Downloads: 3026
Keywords: 


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.



ISSN 1433-8092 | Imprint