On the Average Case Complexity of Some P-complete Problems

Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, Campus Nord – C6, Jordi Girona Salgado 1-3, 08034 Barcelona, Spain; fatos@lsi.upc.es.

Received: July 1997
Accepted: July 1998

Abstract

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.

Résumé

Nous montrons que quelques problèmes classiques qui sont P-complets peuvent être résolus efficacement en average NC. Le mo dèle probabiliste que nous considérons est l'espace de descriptions des entrées du problème sous la distribution uniforme. Nous présentons des algorithmes parallèles qui utilisent un nombre polynomial de processeurs dont leur temps espéré est majoré par (e ln 4 + o(1))log n, assymptotiquement avec haute probabilité, où n est la taille de l'entrée.