| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429736 | Journal of Computer and System Sciences | 2007 | 20 Pages |
Abstract
We show the following results regarding complete sets.•NP-complete sets and PSPACE-complete sets are polynomial-time many–one autoreducible.•Complete sets of any level of PH, MODPH, or the Boolean hierarchy over NP are polynomial-time many–one autoreducible.•EXP-complete sets are polynomial-time many–one mitotic.•If there is a tally language in NP∩coNP−P, then, for every ϵ>0, NP-complete sets are not 2n(1+ϵ)-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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
