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 |

1) Download Document PDF |

Open access Restricted Private