Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis

摘要

Building on a recent breakthrough by Ogihara, we resolve a conjecture made by Hartmanis in 1978 regarding the (non)existence of sparse sets complete for P under logspace many–one reductions. We show that if there exists a sparse hard set for P under logspace many–one reductions, then P=LOGSPACE. We further prove that if P has a sparse hard set under many–one reductions computable in NC1, then P collapses to NC1.