Citation
M. Serna et F. Xhafa, On the average case complexity of some P-complete problems, RAIRO-INF, 33(1), 1999, pp. 33-45
Citations number
16
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS
ISSN journal
09883754
→ ACNP
Volume
33
Issue
1
Year of publication
1999
Pages
33 - 45
Database
ISI
SICI code
0988-3754(199901/02)33:1<33:OTACCO>2.0.ZU;2-3
Abstract
We show that some classical P-complete problems can be solved efficiently i
n average NC. The probabilistic model we consider is the sample space of in
put 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.