Computational ComplexityThis modern introduction to the Theory of Computer Science is the first unified introduction to Computational Complexity. I+ offers a comprehensive and accessible treatment of the theory of algorithms and complexity - the elegant body of concepts and methods developed by computer scientists over the past 30 years for studying the pe@ormance and limitations of computer algorithms. The book is self-contained in that it develops all necessary mathematical prerequisites from such diverse fields such as computability, logic, number theory and probability. |
From inside the book
Results 1-3 of 47
Page 361
Christos H. Papadimitriou. Our goal in parallel algorithms is to achieve such logarithmic , or at least polylogarithmic , such as log3n , step counts . This is the exponential drop in complexity that we hope to obtain from parallel ...
Christos H. Papadimitriou. Our goal in parallel algorithms is to achieve such logarithmic , or at least polylogarithmic , such as log3n , step counts . This is the exponential drop in complexity that we hope to obtain from parallel ...
Page 369
... parallel matrix multiplications , or O ( n1 ) total work . Unfortunately , the matrix elements are not bits , but nth degree polynomials in x . It is easy to see that each ... Parallel Models of Computation 369 Parallel models of computation.
... parallel matrix multiplications , or O ( n1 ) total work . Unfortunately , the matrix elements are not bits , but nth degree polynomials in x . It is easy to see that each ... Parallel Models of Computation 369 Parallel models of computation.
Page 376
... parallel computers , " very much the same way that P has been claimed to capture the intuitive notion of efficient ... parallel computation the more interesting problems require substantial output . ( And , as we shall see later in this ...
... parallel computers , " very much the same way that P has been claimed to capture the intuitive notion of efficient ... parallel computation the more interesting problems require substantial output . ( And , as we shall see later in this ...
Common terms and phrases
3SAT accepting Alice axiom binary bits Boolean circuit Boolean expression Boolean functions bound Chapter clauses complete problems complexity classes Computer Science configuration conjunctive normal form coNP Consider construction Corollary corresponding cursor cycle decides define definition deterministic directed graph edges encoding example exponential false Figure finite first-order first-order logic gadget gates given graph G halts HAMILTON PATH INDEPENDENT SET induction input instance integers L-reduction language Lemma length literals logarithmic space logic matching matrix MAX FLOW MAX-CUT MAXSNP modulo nodes nondeterministic Turing machine normal form Notice number theory optimization problems optimum oracle oracle machine output parallel polynomial hierarchy prime Proc processors proof of Theorem Proposition prove PSPACE PSPACE-complete quantifiers random REACHABILITY recall recursively enumerable reduction result satisfying truth assignment second-order logic Section sequence Show simulated solved steps string subset Suppose symbol true variables