Recently a 1978 conjecture by Hartmanis was resolved by Cai and Sivakumar, following progress made by Ogihara. It was shown that there is no sparse set that is hard for P under logspace many-one-reductions, unless P = LOGSPACE. We extend these results to the case of sparse sets that are hard under more general reducibilities. Furthermore, the proof technique can be applied to resolve open questions about hard sparse sets for NP as well. Using algebraic and probabilistic techniques, we show the following results.
展开▼
