L-Printable Setvs (Extended Abstract)
Lance Fortnow, Judy Goldsmith, Stephen Mahaneyt, Matthew A. Levyt · 1996
Properties of L-printable sets are considered, land at is shown that two sets A and B that are Lprintable and have similar density are L-isomorphic. L-printable sets are characterized as those sets Lisomorphic 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 Lrankable and L-printable sets is considered, and strong indications are given that these classes are all dilferent. An oracle is constructed relative to which there are sparse L-rankable sets that are in L and not Lprintable, and L-rankable sets of similar density that are not L-isomorphic.