PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Codenotti B., Leoncini M., Resta G. On reductions and approximations in parallel algebraic complexity. In: 4th Italian Conference 'Theoretical Computer Science'. (L'Aquila, Italia, 28 - 30 October 1992). Atti, pp. 179 - 188. A. Marchetti Spaccamela, P. Mentrasti and M. Venturini Zilli (eds.). World Scientific, 1992.
 
 
Abstract
(English)
Using a new notion of reducibility we investigate, in an approximate setting, the behaviour of many known parallel reductions among important linear algebraic problems. We prove that, although many such problems have been shown to be NC∆1equivalent, when approximation is taken into account new questions about their relative complexity come up, and some reductions appear not to hold.
Subject


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