On the Average Case Complexity of Some P-complete Problems
Maria Serna, Fatos Xhafa (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We show that some classical P-complete problems can be solved efficiently in 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 ( ln 4 + (1))log , asymptotically with high probability, where is the instance size.