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.
... more >>><p> We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that:</p>
<ul>
<li>1-tt-mitoticity and m-mitoticity differ on NP.</li>
<li>1-tt-reducibility and m-reducibility differ on NP.</li>
<li>There exist non-T-autoreducible sets in NP (by a result from Ambos-Spies, these sets are neither ...
more >>>
We investigate the autoreducibility and mitoticity of complete sets for several classes with respect to different polynomial-time and logarithmic-space reducibility notions.
Previous work in this area focused on polynomial-time reducibility notions. Here we obtain new mitoticity and autoreducibility results for the classes EXP and NEXP with respect to some restricted ... more >>>
We investigate autoreducibility properties of complete sets for \cNEXP under different polynomial reductions.
Specifically, we show under some polynomial reductions that there is are complete sets for
\cNEXP that are not autoreducible. We obtain the following results:
- There is a \reduction{p}{tt}-complete set for \cNEXP that is not \reduction{p}{btt}-autoreducible.
more >>>
We study the autoreducibility and mitoticity of complete sets for NP and other complexity classes, where the main focus is on logspace reducibilities. In particular, we obtain:
- For NP and all other classes of the PH: each logspace many-one-complete set is logspace Turing-autoreducible.
- For P, the delta-levels of ...
more >>>
We study the polynomial-time autoreducibility of NP-complete sets and obtain separations under strong hypotheses for NP. Assuming there is a p-generic set in NP, we show the following:
- For every k \geq 2, there is a k-T-complete set for NP that is k-T autoreducible, but is not k-tt autoreducible ... more >>>