On the average case complexity of some P-complete problems

Maria Serna; Fatos Xhafa

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1999)

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

How to cite

top

Serna, Maria, and Xhafa, Fatos. "On the average case complexity of some P-complete problems." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 33.1 (1999): 33-45. <http://eudml.org/doc/92589>.

@article{Serna1999,
author = {Serna, Maria, Xhafa, Fatos},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {P-complete problems},
language = {eng},
number = {1},
pages = {33-45},
publisher = {EDP-Sciences},
title = {On the average case complexity of some P-complete problems},
url = {http://eudml.org/doc/92589},
volume = {33},
year = {1999},
}

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 - Informatique Théorique et Applications
PY - 1999
PB - EDP-Sciences
VL - 33
IS - 1
SP - 33
EP - 45
LA - eng
KW - P-complete problems
UR - http://eudml.org/doc/92589
ER -

References

top
  1. [1] J. L. Balcázar, J. Díaz and J. Gabarró, Structural complexity II, Springer Verlag (1995). Zbl0826.68048MR1324338
  2. [2] N. Calkin and A. Frieze, Probabilistic analysis of a parallel algorithm for finding a maximal independent set. Random Structures and Algorithrns 1 (1990) 39-50. Zbl0707.68042MR1068490
  3. [3] S. A. Cook, An Observation on time-storage trade-offs. J. Comp. Syst. Sci. 9 (1974) 308-316. Zbl0306.68026MR398160
  4. [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. [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. [6] R. Greenlaw, H. J. Hoover and W. L. Ruzzo, Limits to parallel computation: P-completeness theory. Oxford University Press (1995). Zbl0829.68068MR1333600
  7. [7] J. Hoover and W. Ruzzo, A compendium of problems complete for P. Manuscript (1984). 
  8. [8] N. D. Jones and T. Laaser, Complete problems for deterministic polynomial time. Theoret. Comput. Sci. 3 (1977) 105-117. Zbl0352.68068MR455543
  9. [9] D. E. Knuth, The art of computer programming, Vol. 1. Addison-Wesley (1973). Zbl0302.68010MR378456
  10. [10] D. Kozen, Complexity of finitely presented algebras; in Proc. of 9th ACM STOC (1977) 164-167. MR488999
  11. [11] R. E. Ladner, The circuit value problem is logspace complete for P. SIGACT News 7 (1975) 18-20. 
  12. [12] M. Serna, The parallel approximbility of P-complete problems. PhD thesis, Universitat Politècnica de Catalunya (1990). 
  13. [13] M. Serna, Approximating linear programming is logspace complete for P. Inform. Proc. Lett 37 (1991) 233-236. Zbl0713.90046MR1095711
  14. [14] S. Sahni and T. Gonzalez, P-complete approximation problems. J. Assoc. Comput. Mach. 23 (1976) 555-565. Zbl0348.90152MR408313
  15. [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 Science 401 (1989) 193-204. Zbl0704.68041MR1048163
  16. [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 Science 1136 (1996) 208-220. Zbl0939.68044MR1469233

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.