Free access
Issue
RAIRO-Theor. Inf. Appl.
Volume 33, Number 1, January Fabruary 1999
Page(s) 33 - 45
DOI http://dx.doi.org/10.1051/ita:1999104
Published online 15 August 2002
  1. J.L. Balcázar, J. Díaz and J. Gabarró, Structural complexity II, Springer Verlag (1995).
  2. N. Calkin and A. Frieze, Probabilistic analysis of a parallel algorithm for finding a maximal independent set. Random Structures and Algorithms 1 (1990) 39-50. [CrossRef] [MathSciNet]
  3. S.A. Cook, An Observation on time-storage trade-offs. J. Comp. Syst. Sci. 9 (1974) 308-316. [CrossRef]
  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).
  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. [CrossRef]
  9. D.E. Knuth, The art of computer programming, Vol. 1. Addison-Wesley (1973).
  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 News 7 (1975) 18-20. [CrossRef]
  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. [CrossRef] [MathSciNet]
  14. S. Sahni and T. Gonzalez, P-complete approximation problems. J. Assoc. Comput. Mach. 23 (1976) 555-565. [CrossRef] [MathSciNet]
  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.
  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.