The perspectives of introducing parallelism in computation disclosed by the advent of VLSI technology motivate the development of new interesting branches of the theory of computational complexity. Two basic questions related to parallelism concern the definition of suitable formal models of parallel computation and the characterization of complexity classes with respect to these models. For the second question, it is obvious that the main interest is in establishing which problems can be 'efficiently' parallelized, i. e. can be solved by parallel algorithms substantially faster than by sequential ones. The class NC of these problems has been formally defined as the class of problems which can be solved in O(log**kn) using a polynomial number of processors. This paper contributes to a method for deciding if a given problem can be quickly solved on parallel architectures.
Bertoni, A., Bollina, M., Mauri, G., Sabadini, N. (1985). On characterizing classes of efficiently parallelizable problems. In Proceedings Conference on VLSI: Algorithms and Architectures (pp.13-26). Amsterdam : North Holland.
On characterizing classes of efficiently parallelizable problems
Mauri, G;
1985
Abstract
The perspectives of introducing parallelism in computation disclosed by the advent of VLSI technology motivate the development of new interesting branches of the theory of computational complexity. Two basic questions related to parallelism concern the definition of suitable formal models of parallel computation and the characterization of complexity classes with respect to these models. For the second question, it is obvious that the main interest is in establishing which problems can be 'efficiently' parallelized, i. e. can be solved by parallel algorithms substantially faster than by sequential ones. The class NC of these problems has been formally defined as the class of problems which can be solved in O(log**kn) using a polynomial number of processors. This paper contributes to a method for deciding if a given problem can be quickly solved on parallel architectures.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
