Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Limits to parallel computation
Greenlaw R., Hoover H., Ruzzo W., Oxford University Press, Inc., New York, NY, 1995. Type: Book (9780195085914)
Date Reviewed: Jul 1 1996

Anyone who has used Garey and Johnson’s famous reference [1] will agree that it is indispensable to any computer science library because the theory of NP-completeness is a useful tool, and the book has become this area’s standard manual. The theory of NP-completeness tells us about the worst-case running time of any program we are likely to write to solve an NP-complete problem. NP-complete problems are ubiquitous, so this theory is relevant to people working in almost every segment of computer science. Since it is quicker to look up whether a problem is known to be NP-complete than to come up with a proof of one’s own, a well-organized catalog is handy.

There is more to complexity theory than NP-completeness, however. For instance, there is the question of what can be done quickly and efficiently in parallel. Although useful parallel algorithms have been found for many problems, other important problems have resisted all attempts at parallelization. Complexity theory provides the theory of P-completeness to explain why it seems unlikely that efficient parallel algorithms will ever be found for some of these problems.

Greenlaw, Hoover, and Ruzzo have written an excellent reference manual for using this tool, and one can easily compare it to Garey and Johnson. It will be of interest mainly to the many people working on parallel computation. It lists over 100 P-complete problems, and provides references and useful discussions with each problem. Equally useful is their list of open questions in various categories. I usually find quick answers to questions by using this book. The authors suggest that the book could be used for a one-semester course on parallel computation, but my feeling is that in one semester one would want to cover more than just the topics covered in this book.

The book is divided into two parts: a part covering the theory of P-completeness, and a reference “Compendium” organized along the lines of Garey and Johnson, with sections on topics such as graph theory, optimization, logic, algebra, and geometry. The first five chapters present background and motivation: an introduction; models of parallel computation; the required notions from complexity theory; some P-complete problems; and a discussion of what P-completeness really tells us. Chapter 6 offers useful tools for proving P-completeness results. Chapters 7 and 8 focus on specific classes of algorithms, and on what it means for an algorithm to be hard to parallelize. Chapter 9 discusses alternative notions of P-completeness, and chapter 10 touches on whether approximate solutions are easier to find in parallel than exact solutions. Chapter 11 concludes the first part with some summary remarks.

All the chapters are well written, and the extensive bibliography is useful. The authors have been extremely thorough and careful. Still, it is probably unavoidable that in a project of this size a few errors would arise. To sum up, however, the theory of P-completeness gives us important insights into the nature of the limits of parallel computation, and Greenlaw, Hoover, and Ruzzo have written an excellent reference work. I recommend it highly.

Reviewer:  Eric Allender Review #: CR119417 (9607-0468)
1) Garey, M. and Johnson, D. Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco, 1979. See <CR> 21, 12 (Dec. 1980), Rev. 37,225.
Bookmark and Share
 
Reducibility And Completeness (F.1.3 ... )
 
 
Parallelism And Concurrency (F.1.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Reducibility And Completeness": Date
Simple local search problems that are hard to solve
Schäffer A., Yannakakis M. SIAM Journal on Computing 20(1): 56-87, 1991. Type: Article
Jan 1 1992
On computational complexity and honest polynomial degrees
Downey R. Theoretical Computer Science 78(2): 305-317, 1991. Type: Article
Feb 1 1992
On sets polynomially enumerable by iteration
Hemachandra L., Hoene A., Siefkes D. (ed), Young P. Theoretical Computer Science 80(2): 203-225, 1991. Type: Article
Mar 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy