Deterministic and Randomized Bounded Tru
โ
Dieter van Melkebeek
๐
Article
๐
1998
๐
Elsevier Science
๐
English
โ 545 KB
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 1 , the collapse goes down to P=NC 1 . We parameterize this result and obtain a generic theorem allowing us to vary the sparseness condition, th