# On the Average Case Complexity of Some P-complete Problems

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 33, Issue: 1, page 33-45
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topSerna, Maria, and Xhafa, Fatos. "On the Average Case Complexity of Some P-complete Problems." RAIRO - Theoretical Informatics and Applications 33.1 (2010): 33-45. <http://eudml.org/doc/221996>.

@article{Serna2010,

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.
},

author = {Serna, Maria, Xhafa, Fatos},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {P-complete problems},

language = {eng},

month = {3},

number = {1},

pages = {33-45},

publisher = {EDP Sciences},

title = {On the Average Case Complexity of Some P-complete Problems},

url = {http://eudml.org/doc/221996},

volume = {33},

year = {2010},

}

TY - JOUR

AU - Serna, Maria

AU - Xhafa, Fatos

TI - On the Average Case Complexity of Some P-complete Problems

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 33

IS - 1

SP - 33

EP - 45

AB -
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.

LA - eng

KW - P-complete problems

UR - http://eudml.org/doc/221996

ER -

## References

top- J.L. Balcázar, J. Díaz and J. Gabarró, Structural complexity II, Springer Verlag (1995). Zbl0826.68048
- N. Calkin and A. Frieze, Probabilistic analysis of a parallel algorithm for finding a maximal independent set. Random Structures and Algorithms1 (1990) 39-50. Zbl0707.68042
- S.A. Cook, An Observation on time-storage trade-offs. J. Comp. Syst. Sci.9 (1974) 308-316. Zbl0306.68026
- D. Coppersmith, P. Raghavan and M. Tompa, Parallel graph algorithms that are efficient in average, in Proc. of 28th IEEE Symposium on Foundations of Computer Science (1987) 260-269.
- J. Díaz, M. Serna, P. Spirakis and J. Torán, On the expected depth of Boolean circuits. Technical Report LSI-94-7-R, Universitat Politècnica de Catalunya, Dept. de LSI (1994).
- R. Greenlaw, H.J. Hoover and W.L. Ruzzo, Limits to parallel computation: P-completeness theory. Oxford University Press (1995). Zbl0829.68068
- J. Hoover and W. Ruzzo, A compendium of problems complete for P. Manuscript (1984).
- N.D. Jones and T. Laaser, Complete problems for deterministic polynomial time. Theoret. Comput. Sci.3 (1977) 105-117. Zbl0352.68068
- D.E. Knuth, The art of computer programming, Vol. 1. Addison-Wesley (1973). Zbl0302.68010
- D. Kozen, Complexity of finitely presented algebras; in Proc. of 9th ACM STOC (1977) 164-167.
- R.E. Ladner, The circuit value problem is logspace complete for P. SIGACT News7 (1975) 18-20.
- M. Serna, The parallel approximbility of P-complete problems. PhD thesis, Universitat Politècnica de Catalunya (1990).
- M. Serna, Approximating linear programming is logspace complete for P. Inform. Proc. Lett.37 (1991) 233-236. Zbl0713.90046
- S. Sahni and T. Gonzalez, P-complete approximation problems. J. Assoc. Comput. Mach.23 (1976) 555-565. Zbl0348.90152
- M. Serna and P.G. Spirakis, The approximability of problems complete for P, in International Symposium on Optimal Algorithms, Springer-Verlag, Lecture Notes in Computer Science401 (1989) 193-204. Zbl0704.68041
- T. Tsukiji and F. Xhafa, On the expected depth of randomly generated circuits, J. Díaz and M. Serna Eds., in Proc. of Fourth European Symposium on Algorithms, ESA'96, Springer-Verlag, Lecture Notes in Computer Science1136 (1996) 208-220. Zbl0939.68044

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.