Affiliations: Department of Computer Science, University of Wyoming, 1000 E University Ave, Laramie, WY 82071, USA | Department of Computer Science, University of Wyoming, 1000 E University Ave, Laramie, WY 82071, USA | Department of Computer Science, Iowa State University, 226 Atanasoff Hall, Ames, IA 50011, USA
Abstract: We study the structure of the polynomial-time complete sets for NP and PSPACE under strong nondeterministic polynomial-time reductions (SNP-reductions). We show the following results. • If NP contains a p-random language, then all polynomial-time complete sets for PSPACE are SNP-isomorphic. • If NP∩CoNP contains a p-random language, then all polynomial-time complete sets for NP are SNP-isomorphic.
Keywords: completeness, isomorphism conjecture, resource-bounded measure, SNP reducibility
DOI: 10.3233/COM-140028
Journal: Computability, vol. 3, no. 2, pp. 91-104, 2014
