On randomized reductions to sparse sets
Desh Ranjan, Pankaj Rohatgi · 2003
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.>