On optimal language compression for sets in PSPACE-polyReportar como inadecuado



 On optimal language compression for sets in PSPACE-poly


On optimal language compression for sets in PSPACE-poly - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Descargar gratis o leer online en formato PDF el libro: On optimal language compression for sets in PSPACE-poly
We show that if DTIME2^On is not included in DSPACE2^on, then, for every set B in PSPACE-poly, all strings x in B of length n can be represented by a string compressedx of length at most log|B^{=n}|+Olog n, such that a polynomial-time algorithm, given compressedx, can distinguish x from all the other strings in B^{=n}. Modulo the Olog n additive term, this achieves the information-theoretic optimum for string compression. We also observe that optimal compression is not possible for sets more complex than PSPACE-poly because for any time-constructible superpolynomial function t, there is a set A computable in space tn such that at least one string x of length n requires compressedx to be of length 2 log|A^=n|.



Autor: N. V. Vinodchandran; Marius Zimand

Fuente: https://archive.org/







Documentos relacionados