On the average case complexity of some P-complete problems
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) no. 1, pp. 33-45. 
@article{ITA_1999__33_1_33_0,
     author = {Serna, Maria and Xhafa, Fatos},
     title = {On the average case complexity of some {P-complete} problems},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {33--45},
     publisher = {EDP-Sciences},
     volume = {33},
     number = {1},
     year = {1999},
     mrnumber = {1705854},
     zbl = {0927.68038},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_1999__33_1_33_0/}
}
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
SP  - 33
EP  - 45
VL  - 33
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1999__33_1_33_0/
LA  - en
ID  - ITA_1999__33_1_33_0
ER  - 
%0 Journal Article
%A Serna, Maria
%A Xhafa, Fatos
%T On the average case complexity of some P-complete problems
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1999
%P 33-45
%V 33
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1999__33_1_33_0/
%G en
%F ITA_1999__33_1_33_0
Serna, Maria; Xhafa, Fatos. On the average case complexity of some P-complete problems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) no. 1, pp. 33-45. http://archive.numdam.org/item/ITA_1999__33_1_33_0/

[1] J. L. Balcázar, J. Díaz and J. Gabarró, Structural complexity II, Springer Verlag (1995). | MR

[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. | MR | Zbl

[3] S. A. Cook, An Observation on time-storage trade-offs. J. Comp. Syst. Sci. 9 (1974) 308-316. | MR | Zbl

[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). | MR | Zbl

[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. | MR | Zbl

[9] D. E. Knuth, The art of computer programming, Vol. 1. Addison-Wesley (1973). | MR

[10] D. Kozen, Complexity of finitely presented algebras; in Proc. of 9th ACM STOC (1977) 164-167. | MR

[11] R. E. Ladner, The circuit value problem is logspace complete for P. SIGACT News 7 (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. | MR | Zbl

[14] S. Sahni and T. Gonzalez, P-complete approximation problems. J. Assoc. Comput. Mach. 23 (1976) 555-565. | MR | Zbl

[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. | MR | Zbl

[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. | MR