ECCC-Report TR05-011https://eccc.weizmann.ac.il/report/2005/011Comments and Revisions published for TR05-011en-usFri, 21 Jan 2005 21:47:30 +0200
Paper TR05-011
| Autoreducibility, Mitoticity, and Immunity |
Christian Glaßer,
Mitsunori Ogihara,
A. Pavan,
Alan L. Selman,
Liyu Zhang
https://eccc.weizmann.ac.il/report/2005/011We 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.
Fri, 21 Jan 2005 21:47:30 +0200https://eccc.weizmann.ac.il/report/2005/011