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

Author: van Melkebeek D.

Source: Journal of Computer and System Sciences, Volume 57, Number 2, October 1998 , pp. 213-232(20)

Buy & download fulltext article:

Price: $52.63 plus tax (Refund Policy)

Abstract:

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¹, the collapse goes down to P=NC¹. We parameterize this result and obtain a generic theorem allowing us 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. Copyright 1998 Academic Press.

Language: English

Document Type: Research article

Affiliations: Department of Computer Science, University of Chicago, Chicago, Illinois, 60637

Publication date: 1998-10-01