On the optimal compression of sets in PSPACE

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

2011-04-14

arxiv.org/abs/1104.2816v1

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the optimal compression of sets in PSPACE does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the optimal compression of sets in PSPACE, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the optimal compression of sets in PSPACE will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-167043