SELF-REDUCIBLE, P-SELECTIVE, NEAR-TESTABLE, AND P-CHEATABLE SETS: THE EFFECT OF INTERNAL STRUCTURE ON THE COMPLEXITY OF A SET.

The relationship between certain structural properties of a set and the set's computational complexity is discussed. Four classes of sets are studied for which the membership question for one element of the domain can be related to the membership question of other smaller (with regard to some ordering) elements: self-reducible sets, p-selective sets, near-testable sets and p-cheatable sets. The results suggest that a continuing systematic study of the relationship between this type of internal structure and the computational complexity of a set is in order.