Strong Reductions and Isomorphism of Complete Sets

Ryan C. Harkins, John M. Hitchcock, and A. Pavan

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.

Proceedings of the
27th International Conference on Foundations of Software
Technology and Theoretical Computer Science (New Delhi, India,
December 12-14, 2007),
Lecture Notes in Computer Science 4855, pages 168-178,
Springer-Verlag, 2007.
[DOI]