On the Average Case Complexity of Some P-complete Problems

Maria Serna; Fatos Xhafa

RAIRO - Theoretical Informatics and Applications (2010)

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

Abstract

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

How to cite

top

Serna, 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
  1. J.L. Balcázar, J. Díaz and J. Gabarró, Structural complexity II, Springer Verlag (1995).  Zbl0826.68048
  2. 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
  3. S.A. Cook, An Observation on time-storage trade-offs. J. Comp. Syst. Sci.9 (1974) 308-316.  Zbl0306.68026
  4. 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.  
  5. 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).  
  6. R. Greenlaw, H.J. Hoover and W.L. Ruzzo, Limits to parallel computation: P-completeness theory. Oxford University Press (1995).  Zbl0829.68068
  7. J. Hoover and W. Ruzzo, A compendium of problems complete for P. Manuscript (1984).  
  8. N.D. Jones and T. Laaser, Complete problems for deterministic polynomial time. Theoret. Comput. Sci.3 (1977) 105-117.  Zbl0352.68068
  9. D.E. Knuth, The art of computer programming, Vol. 1. Addison-Wesley (1973).  Zbl0302.68010
  10. D. Kozen, Complexity of finitely presented algebras; in Proc. of 9th ACM STOC (1977) 164-167.  
  11. R.E. Ladner, The circuit value problem is logspace complete for P. SIGACT News7 (1975) 18-20.  
  12. M. Serna, The parallel approximbility of P-complete problems. PhD thesis, Universitat Politècnica de Catalunya (1990).  
  13. M. Serna, Approximating linear programming is logspace complete for P. Inform. Proc. Lett.37 (1991) 233-236.  Zbl0713.90046
  14. S. Sahni and T. Gonzalez, P-complete approximation problems. J. Assoc. Comput. Mach.23 (1976) 555-565.  Zbl0348.90152
  15. 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
  16. 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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.