A binary sequence A=A(0)A(1).... is called i.o. Turing-autoreducible if A is reducible to itself via an oracle Turing machine that never queries its oracle at the current input, outputs either A(x) or a don't-know symbol on any given input x, and outputs A(x) for infinitely many x. If in addition ... more >>>

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 ... more >>>

We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that:

• 1-tt-mitoticity and m-mitoticity differ on NP.
• 1-tt-reducibility and m-reducibility differ on NP.
• There exist non-T-autoreducible sets in NP (by a result from Ambos-Spies, these sets are neither T-mitotic nor m-mitotic).
... more >>>