Abstract
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 language | English |
|---|---|
| Pages (from-to) | 97-106 |
| Number of pages | 10 |
| Journal | Proceedings of the Annual IEEE Conference on Computational Complexity |
| State | Published - 1996 |
| Event | Proceedings of the 1996 11th Annual IEEE Conference on Computational Complexity - Philadelphia, PA, USA Duration: May 24 1996 → May 27 1996 |
ASJC Scopus subject areas
- Software
- Theoretical Computer Science
- Computational Mathematics