Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Autoreducibility, Mitoticity, And Immunity, Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang
Autoreducibility, Mitoticity, And Immunity, Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang
Computer Science Faculty Publications and Presentations
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 2 n ( 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.