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.