- Author: D. van Melkebeek.
- Reference:
*Journal of Computer and System Sciences*, 57(2): 213-232, 1998. Special issue for selected papers from the 11th IEEE Conference on Computational Complexity. - Earlier version:
- Reducing P to a Sparse Set
Using a Constant Number of Queries Collapses P to L.
In
*Proceedings of the 11th IEEE Conference on Computational Complexity*, pages 88-96, 1996.

- Reducing P to a Sparse Set
Using a Constant Number of Queries Collapses P to L.
In

We parameterize this result and obtain a generic theorem allowing to vary the sparseness condition, the space bound and the number of queries of the truth-table reduction. Another instantiation yields that there is no quasipolynomially dense hard set for P under polylog-space computable truth-table reductions using polylogarithmically many queries unless P is in polylog-space.

We also apply the proof technique to NL and L. We establish that
there is no sparse hard set for NL under logspace computable
bounded truth-table reductions unless NL = L, and that
there is no sparse hard set for L under NC^{1}-computable
bounded truth-table reductions unless L = NC^{1}.

We show that all these results carry over to the randomized setting: If we allow two-sided error randomized reductions with confidence at least inversely polynomial, we obtain collapses to the corresponding randomized classes in the multiple access model. In addition, we prove that there is no sparse hard set for NP under two-sided error randomized polynomial-time bounded truth-table reductions with confidence at least inversely polynomial unless NP = RP.

dieter@cs.wisc.edu