Istituto di Scienza e Tecnologie dell'Informazione     
Codenotti B., Leoncini M., Resta G. A note on some parallel algebraic complexity classes. Internal note IEI-B4-01, 1991.
In this note we observe that the known reduction "determinant" to "linear system solution" in Csanky's work is P-complete, and thus hardly (i.e. unless P=NC) computable in polylog time with a polynomial number of processors. This fact gives rise to a new strtuctural hypotesis for some classes of matrix problems.

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional