
Limits to Parallel Computation
P-Completeness Theory
Oxford University Press Inc
Published on 1. June 1995
Book
Hardback
336 pages
978-0-19-508591-4 (ISBN)
Description
This volume provides an ideal introduction to key topics in parallel computing.
With its cogent overview of the essentials of the subject as well as lists of P -complete- and open problems, extensive remarks corresponding to each problem, a thorough index, and extensive references, the book will prove invaluable to programmers stuck on problems that are particularly difficult to parallelize. In providing an up-to-date survey of parallel computing research from 1994, Topics in Parallel Computing will prove invaluable to researchers and professionals with an interest in the super computers of the future.
With its cogent overview of the essentials of the subject as well as lists of P -complete- and open problems, extensive remarks corresponding to each problem, a thorough index, and extensive references, the book will prove invaluable to programmers stuck on problems that are particularly difficult to parallelize. In providing an up-to-date survey of parallel computing research from 1994, Topics in Parallel Computing will prove invaluable to researchers and professionals with an interest in the super computers of the future.
Reviews / Votes
an excellent reference manual. ... All the chapters are well written, and the extensive bibliography is useful. The authors have been extremely thorough and careful. ... 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. * Eric Allender, Computing Reviews, July 1996. *More details
Language
English
Place of publication
New York
United States
Target group
Professional and scholarly
Illustrations
line figures
Dimensions
Height: 235 mm
Width: 157 mm
Thickness: 24 mm
Weight
685 gr
ISBN-13
978-0-19-508591-4 (9780195085914)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Other editions
Additional editions

Raymond Greenlaw | H. James Hoover | Walter L. Ruzzo
Limits to Parallel Computation
P-Completeness Theory
E-Book
04/1995
1st Edition
OUP eBook
€162.99
Available for download
Persons
Author
Assistant Professor, Department of Computer ScienceAssistant Professor, Department of Computer Science, University of New Hampshire
Associate Professor, Department of Computer ScienceAssociate Professor, Department of Computer Science, University of Alberta
Professor, Department of Computer ScienceProfessor, Department of Computer Science, University of Washington
Content
PART I: Background and Theory
1: Introduction
2: Parallel Models and Complexity Classes
3: Two Basic P-Complete Problems
4: Evidence that NC Does Not Equal P
5: The Circuit Value Problem
6: Parallel Versions of Sequential Paradigms
7: Boolean Circuits
PART II: P-Complete and Open Problems
8: List of P-Complete Problems
9: Open Problems
1: Introduction
2: Parallel Models and Complexity Classes
3: Two Basic P-Complete Problems
4: Evidence that NC Does Not Equal P
5: The Circuit Value Problem
6: Parallel Versions of Sequential Paradigms
7: Boolean Circuits
PART II: P-Complete and Open Problems
8: List of P-Complete Problems
9: Open Problems