We show the following results regarding complete sets.

• NP-complete sets and PSPACE-complete sets are many-one autoreducible.
• Complete sets of any level of PH, MODPH, or the Boolean hierarchy over NP are many-one autoreducible.
• EXP-complete sets are many-one mitotic.
• NEXP-complete sets are weakly many-one mitotic.
• PSPACE-complete sets are weakly Turing-mitotic.
• If one-way permutations and quick pseudo-random generators exist, then NP-complete languages are m-mitotic.
• If there is a tally language in NP &cap CoNP - P, then, for every &epsilon > 0, NP-complete sets are not 2^{n(1+&epsilon)}-immune.

These results solve several of the open questions raised by Buhrman and Torenvliet in their 1994 survey paper on the structure of complete sets.

• Journal of Computer System and Sciences, To appear.
• 30th International Symposium on Mathematical Foundations of Computer Science , LNCS 3618, 387--398 (2005).