Autoreducibility, mitoticity, and immunity

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

doi:10.1016/j.jcss.2006.10.020

Back

Autoreducibility, mitoticity, and immunity

Journal article

Open access

Peer reviewed

Autoreducibility, mitoticity, and immunity

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

Journal of computer and system sciences, Vol.73(5), pp.735-754

2007

DOI: https://doi.org/10.1016/j.jcss.2006.10.020

Abstract

Autoreducibility

Complete sets

Immunity

Mitoticity

Weak mitoticity

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.

Files and links (1)

url

https://doi.org/10.1016/j.jcss.2006.10.020View

Published (Version of record) Open

Metrics

3 Record Views

15 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types: Domestic collaboration; International collaboration
Citation topics: 4 Electrical Engineering, Electronics & Computer Science; 4.182 Data Structures, Algorithms & Complexity; 4.182.1226 Computability
Web Of Science research areas: Computer Science, Hardware & Architecture; Computer Science, Theory & Methods
ESI research areas: Computer Science

UN Sustainable Development Goals (SDGs)

This output has contributed to the advancement of the following goals:

Source: InCites

Details

Title: Autoreducibility, mitoticity, and immunity
Creators: Christian Glaßer - Lehrstuhl für Theoretische Informatik, Universität Würzburg, Germany
Mitsunori Ogihara - Department of Computer Science, University of Rochester, USA
A Pavan - Department of Computer Science, Iowa State University, USA
Alan L Selman - Department of Computer Science and Engineering, University at Buffalo, USA
Liyu Zhang - Department of Computer Science, University at Buffalo, USA
Publication Details: Journal of computer and system sciences, Vol.73(5), pp.735-754
Publisher: Elsevier Inc
Academic Unit: College of A&S; A&S - Computer Science
Language: English
Resource Type: Journal article
Record Identifier: 991031615268602976