DIMACS Seminar


The Resolution of a Hartmanis Conjecture--Recent Progress on P-hard Sparse Sets


Jin-yi Cai
Department of Computer Science
SUNY - Buffalo


DIMACS Seminar Room 431, CoRE Building, Busch Campus
Rutgers University


10:30 AM (with a continuation after a break for lunch)
Tuesday, June 6, 1995


A set $S$ is called sparse if there are at most a polynomial number of strings in $S$ up to length $n$. Sparse sets have been the subject of study in complexity theory for the past 20 years, as they reveal inherent structure and limitations of computation. For instance, it is well known that the class of languages Cook reducible to a sparse set is precisely the class of languages with polynomial size circuits. Some fundamental results concerning the existence of sparse sets hard for various classes: Karp and Lipton proved that if a Turing hard sparse set exists for NP, then the polynomial time hierarchy collapses to its second level $\Sigma_2^p$. Mahaney showed that if a sparse set exists which is hard for NP under many-one reductions, then P = NP.

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.

Document last modified on May 23, 1995