Hartmanis conjectured in 1978 that there are no sparse complete sets for P under logspace many-one reductions. We resolve this conjecture of Hartmanis. The following theorem will be presented: If a P-hard sparse set exists under logspace reductions, then P = LOGSPACE. An interesting aspect of our work is that the techniques we employ are probabilistic and algebraic in nature.
Following recent work by M. Ogihara, we first show that if a sparse set exists for P under log-space reductions, then $P = NC^2$. We will first give a randomized construction that shows $P = {\cal R}NC^2$, under the given hypothesis. Then we use techniques from finite field theory to provide a deterministic construction. The techniques are relavant to constructions of small sample spaces.
Then a string of improvements and ramifications to other topics in complexity theory will be presented. The final result collapses $P$ to $NC^1$. Our proofs for this final stage uses more of finite field theory, error correcting codes, and discrete Fourier transform. If time permit we will also present other exciting development on the existence of sparse sets hard for P under various weak reductions such as bounded truth table reductions.
Supported by NSF grant CCR9319393 and CCR9057486, and a Sloan fellowship. Joint work with D. Sivakumar of SUNY Buffalo. And joint work with Ashish Naik and D. Sivakumar.