ContactPerson: selman@cse.buffalo.edu Remote host: selman.cse.buffalo.edu ### Begin Citation ### Do not delete this line ### %R 2004-22 %U /web/faculty/selman/auto.ps %A Glasser, Christian %A Ogihara, Mitsunori %A Pavan, A. %A Selman, Alan L. %A Zhang, Liyu %T Autoreducibility, Mitoticity, and Immunity %D December 21, 2004 %I Department of Computer Science and Engineering, SUNY Buffalo %K autoreducibility, mitoticity, immunity %X 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.