Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-011 | 21st December 2004 00:00

Autoreducibility, Mitoticity, and Immunity

RSS-Feed




TR05-011
Authors: Christian Gla├čer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang
Publication: 21st January 2005 21:47
Downloads: 1327
Keywords: 


Abstract:

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 one-way permutations and quick pseudo-random generators exist,
then NP-complete languages are m-mitotic.

If there is a tally language in NP \cap coNP - P, then, for
every \epsilon > 0,
NP-complete sets are not 2^{n(1+\epsilon)}-immune.

These results solve several of the open questions raised by Buhrman and
Torenvliet in their 1994 survey paper on the
structure of complete sets.



ISSN 1433-8092 | Imprint