scientific article; zbMATH DE number 4092771

From MaRDI portal
Publication:3820005





[For the entire collection see Zbl 0658.00013.] The paper classifies the problems solvable very fast in parallel with a feasible number of processors and contrasts them with problems hard to parallelize. The notions of \(NC^ 1\)-reducibilities, \(RNC^ 1\)- reducibilities, log-space reducibilities are presented and problems complete (or randomly complete) for P are defined and discussed. The notion of optimal parallel time-number of processors tradeoff is highlighted and several techniques to achieve optimal tradeoff are presented. Several results about fast parallel approximations to P- complete problems are described. Finally, certain milestones in the design of efficient parallel algorithms are noted and their impact is discussed.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3820005)