文件名称：Limits to Parallel Computation
文件大小：1.15MB
文件格式：PDF
更新时间：2016-06-25 17:25:57
Algorithm
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 ?