E-Book Overview
This book provides a comprehensive analysis of the most important topics in parallel computation. It is written so that it may be used as a self-study guide to the field, and researchers in parallel computing will find it a useful reference for many years to come. The first half of the book consists of an introduction to many fundamental issues in parallel computing. The second half provides lists of P-complete- and open problems. These lists will have lasting value to researchers in both industry and academia. The lists of problems, with their corresponding remarks, the thorough index, and the hundreds of references add to the exceptional value of this resource. While the exciting field of parallel computation continues to expand rapidly, this book serves as a guide to research done through 1994 and also describes the fundamental concepts that new workers will need to know in coming years. It is intended for anyone interested in parallel computing, including senior level undergraduate students, graduate students, faculty, and people in industry. As an essential reference, the book will be needed in all academic libraries.
E-Book Content
Limits to Parallel Computation: P-Completeness Theory RAYMOND GREENLAW University of New Hampshire
H. JAMES HOOVER University of Alberta
WALTER L. RUZZO University of Washington
New York Oxford OXFORD UNIVERSITY PRESS 1995
This book is dedicated to our families, who already know that life is inherently sequential.
Preface This book is an introduction to the rapidly growing theory of P completeness — 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. That is, algorithm designers have failed to find NC algorithms, feasible highly parallel solutions that take time polynomial in the logarithm of the problem size while using only a polynomial number of processors, for them. Consequently, the promise of parallel computation, namely that applying more processors to a problem can greatly speed its solution, appears to be broken by the entire class of P -complete problems. This state of affairs is succinctly expressed as the following question: Does P equal NC ?
Organization of the Material The book is organized into two parts: an introduction to P completeness theory, and a catalog of P -complete and open problems. The first part of the book is a thorough introduction to the theory of P -completeness. We begin with an informal introduction. Then we discuss the major parallel models of computation, describe the classes NC and P , and present the notions of reducibility and completeness. We subsequently introduce some fundamental P -complete problems, followed by evidence suggesting why NC does not equal P . Next, we discuss in detail the primary P -complete problem, that of evaluating a Boolean circuit. Following this we examine several sequential paradigms and their parallel versions. We describe a model for classifying algorithms as inherently sequential. We finish Part I with some general conclusions about practical parallel computation.
viii
PREFACE
Because of the broad range of topics in the rapidly growing field of parallel computation, we are unable to provide a detailed treatment of several related topics. For example, we are unable to discuss parallel algorithm design and development in detail. For important and broad topics like this, we provide the reader with some references to the available literature. The second part of the book provides a comprehensive catalog of P -complete problems, including several unpublished and new P completeness results. For each problem we try to provide the essential idea underlying its P -complete reduct