Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > AUTOREDUCIBILITY:
Reports tagged with autoreducibility:
TR02-056 | 19th September 2002
Todd Ebert, Wolfgang Merkle, Heribert Vollmer

#### On the Autoreducibility of Random Sequences

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

TR05-011 | 21st December 2004
Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang

#### Autoreducibility, Mitoticity, and Immunity

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

TR06-090 | 22nd June 2006
Christian Glaßer, Alan L. Selman, Stephen Travers, Liyu Zhang

#### Non-Mitotic Sets

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

TR13-047 | 27th March 2013
Christian Glaßer, Dung Nguyen, Christian Reitwießner, Alan Selman, Maximilian Witek

#### Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions

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

TR13-063 | 19th April 2013
Dung Nguyen, Alan Selman

#### Non-autoreducible Sets for NEXP

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

TR13-188 | 13th December 2013
Christian Glaßer, Maximilian Witek

#### Autoreducibility and Mitoticity of Logspace-Complete Sets for NP and Other Classes

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

TR16-012 | 21st January 2016