P-printable sets arise naturally in the studies of generalized Kolmogorov complexity and data compression, as well as in other areas. We present new characterization of the P-printable sets and present necessary and sufficient conditions for the existence of sparse sets in P that are not P-printable. As a corollary to one of our results, we show that the class of sets of small generalized Kolmogorov complexity is exactly the class of sets which are P-isomorphic to a tally language.
|Original language||English (US)|
|Number of pages||10|
|Journal||SIAM Journal on Computing|
|State||Published - 1988|
All Science Journal Classification (ASJC) codes
- Computer Science(all)