Complexity-class-encoding sets

Properties of sets which are complex because they encode complexity classes are explored. It is shown that not all sets with inherent complexity are of this type, although this is the only type of set for which well-developed techniques exist for proving inherent complexity. Possibilities for the complexity of encoding sets are discussed, first with reference to an "almost everywhere " vs. "infinitely many arguments " classification, and later with reference to the density of the set of arguments on which the problem is complex. It is shown that relative complexity relationships among sets of this type are highly structured, in contrast o the wide variation possible among arbitrary recursive sets. 1