Autoreducibility, mitoticity, and immunity

摘要

We show the following results regarding complete sets.•NP-complete sets and PSPACE-complete sets are polynomial-time many–one autoreducible.•Complete sets of any level of PH, MODPH, or the Boolean hierarchy over NP are polynomial-time many–one autoreducible.•EXP-complete sets are polynomial-time many–one mitotic.•If there is a tally language in , then, for every , NP-complete sets are not -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.