On the Average Case Complexity of Some P-complete Problems

We show that some classical P-complete problems can be solved efficiently in average NC. The probabilistic model we consider is the sample space of input descriptions of the problem with the underlying distribution being the uniform one. We present parallel algorithms that use a polynomial number of processors and have expected time upper bounded by (e ln 4 + o(1))log n, asymptotically with high probability, where n is the instance size