@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://www.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://www.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://www.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://www.numdam.org/item/ITA_1999__33_1_33_0/
[1] Structural complexity II, Springer Verlag (1995). | MR
, and ,[2] Probabilistic analysis of a parallel algorithm for finding a maximal independent set. Random Structures and Algorithrns 1 (1990) 39-50. | MR | Zbl
and ,[3] An Observation on time-storage trade-offs. J. Comp. Syst. Sci. 9 (1974) 308-316. | MR | Zbl
,[4] Parallel graph algorithms that are efficient in average, in Proc. of 28th IEEE Symposium on Foundations of Computer Science (1987) 260-269.
, and ,[5] On the expected depth of Boolean circuits. Technical Report LSI-94-7-R, Universitat Politècnica de Catalunya, Dept. de LSI (1994).
, , and ,[6] Limits to parallel computation: P-completeness theory. Oxford University Press (1995). | MR | Zbl
, and ,[7] A compendium of problems complete for P. Manuscript (1984).
and ,[8] Complete problems for deterministic polynomial time. Theoret. Comput. Sci. 3 (1977) 105-117. | MR | Zbl
and ,[9] The art of computer programming, Vol. 1. Addison-Wesley (1973). | MR
,[10] Complexity of finitely presented algebras; in Proc. of 9th ACM STOC (1977) 164-167. | MR
,[11] The circuit value problem is logspace complete for P. SIGACT News 7 (1975) 18-20.
,[12] The parallel approximbility of P-complete problems. PhD thesis, Universitat Politècnica de Catalunya (1990).
,[13] Approximating linear programming is logspace complete for P. Inform. Proc. Lett 37 (1991) 233-236. | MR | Zbl
,[14] P-complete approximation problems. J. Assoc. Comput. Mach. 23 (1976) 555-565. | MR | Zbl
and ,[15] 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
and ,[16] 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
and ,