Todd Ebert, Wolfgang Merkle, Heribert Vollmer

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

Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang

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 >>>Christian Glaßer, Alan L. Selman, Stephen Travers, Liyu Zhang

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

Christian Glaßer, Dung Nguyen, Christian Reitwießner, Alan Selman, Maximilian Witek

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

Dung Nguyen, Alan Selman

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

Christian Glaßer, Maximilian Witek

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

John Hitchcock, Hadi Shafei

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