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.
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.

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