On the average complexity of some P-complete problems

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/82485

Title:	On the average complexity of some P-complete problems
Author:	Serna Iglesias, María José; Xhafa Xhafa, Fatos
Other authors:	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
Abstract:	We show that some P-complete problems can be solved efficiently in average NC. The probabilistic model we consider is the sample space of input instances with underlying distribution the uniform one. The parallel algorithms use a polynomial number of processors and have expected time polylogarithmic in instance size.
Subject(s):	-Àrees temàtiques de la UPC::Informàtica -Complexity -P-complet problems
Rights:
Document type:	Article - Published version Report
Share: