Autoreducibility, Mitoticity, and Immunity

Christian Glaßer; Mitsunori Ogihara; A Pavan; Alan L Selman; Liyu Zhang

doi:10.1007/11549345_34

Back

Autoreducibility, Mitoticity, and Immunity

Book chapter

Peer reviewed

Autoreducibility, Mitoticity, and Immunity

Christian Glaßer, Mitsunori Ogihara, A Pavan, Alan L Selman and Liyu Zhang

Mathematical Foundations of Computer Science 2005, pp.387-398

Lecture Notes in Computer Science, Springer Berlin Heidelberg

2005

DOI: https://doi.org/10.1007/11549345_34

Abstract

Boolean Hierarchy

Regular Language

SIAM Journal

Turing Machine

Unconditional Result

We 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 ∩ 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.

Metrics

7 Record Views

Details

Title: Autoreducibility, Mitoticity, and Immunity
Creators: Christian Glaßer - Universität Würzburg,
Mitsunori Ogihara - University of Rochester,
A Pavan - Iowa State University,
Alan L Selman - University at Buffalo,
Liyu Zhang - University at Buffalo,
Publication Details: Mathematical Foundations of Computer Science 2005, pp.387-398
Series: Lecture Notes in Computer Science
Publisher: Springer Berlin Heidelberg; Berlin, Heidelberg
ISSN: 1611-3349
Academic Unit: College of A&S; A&S - Computer Science
Language: English
Resource Type: Book chapter
Record Identifier: 991031615233602976