P-printable sets

Eric W. Allender, Roy S. Rubinstein

Research output: Contribution to journalArticlepeer-review

64 Scopus citations


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 languageEnglish (US)
Pages (from-to)1193-1202
Number of pages10
JournalSIAM Journal on Computing
Issue number6
StatePublished - 1988

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)


Dive into the research topics of 'P-printable sets'. Together they form a unique fingerprint.

Cite this