supervised by:

This thesis reviews selected topics from the theory of parallel computa-tion. The research begins with a survey of the proposed models of parallel computation. It examines the characteristics of each model and it discusses its use either for theoretical studies, or for practical applications. Subse-quently, it employs common simulation techniques to evaluate the computa-tional power of these models. The simulations establish certain model rela-tions before advancing to a detailed study of the parallel complexity theory, which is the subject of the second part of this thesis. The second part exam-ines classes of feasible highly parallel problems and it investigates the limits of parallelization. It is concerned with the benefits of the parallel solutions and the extent to which they can be applied to all problems. It analyzes the parallel complexity of various well-known tractable problems and it discusses the automatic parallelization of the efficient sequential algorithms. Moreover, it compares the models with respect to the cost of realizing parallel solutions