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]