Carregant...
Carregant...

Vés al contingut (premeu Retorn)

On the average complexity of some P-complete problems

Autor
Serna, M.; Xhafa, F.
Tipus d'activitat
Article en revista
Revista
RAIRO. Theoretical informatics and applications
Data de publicació
1999-01
Volum
33
Número
1
Pàgina inicial
33
Pàgina final
45
DOI
https://doi.org/10.1051/ita:1999104 Obrir en finestra nova
URL
https://www.rairo-ita.org/articles/ita/abs/1999/01/ita9903/ita9903.html Obrir en finestra nova
Resum
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.
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants