ContactPerson: selman@cse.buffalo.edu
Remote host: selman.cse.buffalo.edu
### Begin Citation ### Do not delete this line ###
%R 2005-18
%U /tmp/redundancy.pdf
%A Glasser, Christian
%A Pavan, A.
%A Selman, Alan L.
%A Zhang, Liyu
%T Redundancy in Complete Sets
%D July 07, 2005
%I Department of Computer Science and Engineering, SUNY Buffalo
%K mitotic sets, autoreducibility, complete sets
%X We show that a set is m-autoreducible if and only if it is m-mitotic.
This solves a long standing open question in a surprising way.
As a consequence of this unconditional result and recent work
by Gla{\ss}er et al.,
complete sets for all of the following complexity
classes are m-mitotic:
NP, coNP, $\oplus P$, PSPACE, and NEXP,
as well as all levels of PH, MODPH,
and the Boolean hierarchy overNP.
In the cases of NP PSPACE, NEXP, and PH,
this at once answers several well-studied open questions.
These results tell us that complete sets share a redundancy
that was not known before.
We disprove the equivalence between
autoreducibility and mitoticity for all polynomial-time-bounded
reducibilities between 3-tt-reducibility and Turing-reducibility:
There exists a sparse set in EXP that is
polynomial-time 3-tt-autoreducible,
but not weakly polynomial-time T-mitotic.
In particular, polynomial-time T-autoreducibility does not imply
polynomial-time weak T-mitoticity, which solves an open question
by Buhrman and Torenvliet.
We generalize autoreducibility to define poly-autoreducibility
and give evidence that NP-complete sets are poly-autoreducible.