On the Average Case Complexity of Some P-complete Problems
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 33, Issue: 1, page 33-45
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topSerna, 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- J.L. Balcázar, J. Díaz and J. Gabarró, Structural complexity II, Springer Verlag (1995).
- N. Calkin and A. Frieze, Probabilistic analysis of a parallel algorithm for finding a maximal independent set. Random Structures and Algorithms1 (1990) 39-50.
- S.A. Cook, An Observation on time-storage trade-offs. J. Comp. Syst. Sci.9 (1974) 308-316.
- 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.
- 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).
- R. Greenlaw, H.J. Hoover and W.L. Ruzzo, Limits to parallel computation: P-completeness theory. Oxford University Press (1995).
- J. Hoover and W. Ruzzo, A compendium of problems complete for P. Manuscript (1984).
- N.D. Jones and T. Laaser, Complete problems for deterministic polynomial time. Theoret. Comput. Sci.3 (1977) 105-117.
- D.E. Knuth, The art of computer programming, Vol. 1. Addison-Wesley (1973).
- D. Kozen, Complexity of finitely presented algebras; in Proc. of 9th ACM STOC (1977) 164-167.
- R.E. Ladner, The circuit value problem is logspace complete for P. SIGACT News7 (1975) 18-20.
- M. Serna, The parallel approximbility of P-complete problems. PhD thesis, Universitat Politècnica de Catalunya (1990).
- M. Serna, Approximating linear programming is logspace complete for P. Inform. Proc. Lett.37 (1991) 233-236.
- S. Sahni and T. Gonzalez, P-complete approximation problems. J. Assoc. Comput. Mach.23 (1976) 555-565.
- 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.
- 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.
NotesEmbed ?
topYou 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.