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 NC~1, then P collapses to NC~1.