ECCC-Report TR11-069https://eccc.weizmann.ac.il/report/2011/069Comments and Revisions published for TR11-069en-usFri, 29 Apr 2011 10:41:25 +0300
Paper TR11-069
| On the optimal compression of sets in PSPACE |
Marius Zimand
https://eccc.weizmann.ac.il/report/2011/069We 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. Fri, 29 Apr 2011 10:41:25 +0300https://eccc.weizmann.ac.il/report/2011/069