Reducing P to a sparse set using a constant number of queries collapses P to L
Dieter van Melkebeek · 2002
We prove that there is no sparse hard set for P under logspace computable bounded truth-table reductions unless P=L. In case of reductions computable in NC/sup 1/, the collapse goes down to P=NC/sup 1/. We generalize this result by parameterizing the sparseness condition, the space bound and the number of queries of the reduction, apply the proof technique to NL and L, and extend all these theorems to two-sided error randomized reductions in the multiple access model, for which we also obtain new results for NP.