Title :
On randomized reductions to sparse sets
Author :
Ranjan, Desh ; Rohatgi, Pankaj
Author_Institution :
Dept. of Comput. Sci., Cornell Univ., Ithaca, NY, USA
Abstract :
It is shown that the existence of a sparse set that is hard for the class NP under certain randomized reductions implies that NP=RP and hence all languages in the polynomial-time hierarchy can be recognized feasibly. This provides strong evidence for the nonexistence of such sets
Keywords :
computability; computational complexity; NP-hard classes; polynomial-time hierarchy; randomized reductions; sparse sets; Artificial intelligence; Complexity theory; Computer science; Polynomials;
Conference_Titel :
Structure in Complexity Theory Conference, 1992., Proceedings of the Seventh Annual
Conference_Location :
Boston, MA
Print_ISBN :
0-8186-2955-X
DOI :
10.1109/SCT.1992.215397
