Deterministic and Randomized Bounded Truth-table Reductions of P, NL, and L to Sparse Sets

• 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.

Abstract

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¹-computable bounded truth-table reductions unless L = NC¹.

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.