Advertisement
Published in:
2006 | OriginalPaper | Chapter
Redundancy in Complete Sets
Authors : Christian Glaßer, A. Pavan, Alan L. Selman, Liyu Zhang
Published in: STACS 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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ßer et al. [12], complete sets for all of the following complexity classes are m-mitotic: NP, coNP,
$\bigoplus$
P, PSPACE, and NEXP, as well as all levels of PH, MODPH, and the Boolean hierarchy over NP. 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. In particular, every NP-complete set
A
splits into two NP-complete sets
A
1
and
A
2
.