Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with mitoticity:
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

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

Comments: 1

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

ISSN 1433-8092 | Imprint