## DIMACS TR: 96-39

## Deterministic and Randomized Bounded Truth-table

Reductions of
P, NL, and L to Sparse Sets

### Author: Dieter van Melkebeek

**
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 NC1, the collapse goes down to P = NC1.
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 NC1-computable bounded truth-table reductions
unless L = NC1.

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.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-39.ps.gz

DIMACS Home Page