Portal de Periódicos da CAPES

Know your limits (review of "limits to parallel computation: p-completeness theory"; greenlaw, r., et al; 1995) [book review]

2013; Institute of Electrical and Electronics Engineers; Volume: 30; Issue: 1 Linguagem: Inglês

10.1109/mdat.2012.2237133

2168-2364

Igor L. Markov,

Computability, Logic, AI Algorithms

Presents a review of "Limits to Parallel Computation: PCompleteness Theory," by Raymond Greenlaw, H. James Hoover, Walter L. Ruzzo. (Oxford University Press, 1995, ISBN-10: 0195085914, ISBN-13: 978-0195085914). It may seem unusual to review a book published 18 years ago. However, some books are ahead of their time, and some prospective readers may have gotten behind the curve. To this end, the development of commercial parallel software is clearly lagging behind initial hopes and promises, perhaps because known limits to parallel computation have been overlooked. This book is an introduction to the rapidly growing theory of P-completeness - being the branch of complexity theory that focuses on identifying the "hardest" problems in the class P of problems solvable in polynomial time. P-complete problems are of interest because they all appear to lack highly parallel solutions.