Sage Journals: Discover world-class research

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

Get full access to this article

View all access options for this article.

Strong Reductions and Isomorphism of Complete Sets

Abstract

Keywords

Get full access to this article