This research attempts to gain a better understanding of the intrinsic properties of complete sets for many natural complexity classes. The research will explore how the complexity-theoretic properties of complete sets are affected by the strength of the reducibilities defining them, and the relationships between these properties and the central problems in complexity theory. One such property is immunity, which examines whether all complete problems have larger subproblems which are easier to solve than the full problem. This research bears upon the existence of certain types of approximations to these intractable sets. Another area of study is the strength of efficient reductions between pairs of complete sets and the possibility of reductions from complete sets to sparse sets or other sets with a particular structure. The relationships between the complexity-theoretic results in these areas and other current research problems such as the isomorphism problem and the existence of certain types of one-way functions are a central focus of this work.
