Complexity-class-encoding sets

摘要

Properties of sets which are complex because they encode complexity classes areexplored. 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 referenceto 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 highlystructured, in contrast to the wide variation possible among arbitrary recursive sets.