L-printable sets

Lance Fortnow, Judy Goldsmith, Stephen Mahaney

Research output: Contribution to journalConference articlepeer-review


Properties of L-printable sets are considered, and it is shown that two sets A and B that are L-printable and have similar density are L-isomorphic. L-printable sets are characterized as those sets L-isomorphic to tally sets in L, and as subsets of KS[k log n, k log n]. Several classes of L-printable sets are given, including sparse regular and context-free sets; a characterization of sparse regular sets is given. The relationship of the sparse sets in L to the sparse L-rankable and L-printable sets is considered, and strong indications are given that these classes are all different. An oracle is constructed relative to which there are sparse L-rankable sets that are in L and not L-printable, and L-rankable sets of similar density that are not L-isomorphic.

Original languageEnglish
Pages (from-to)97-106
Number of pages10
JournalProceedings of the Annual IEEE Conference on Computational Complexity
StatePublished - 1996
EventProceedings of the 1996 11th Annual IEEE Conference on Computational Complexity - Philadelphia, PA, USA
Duration: May 24 1996May 27 1996

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Computational Mathematics


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

Cite this