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 89
Page 38
... integers , contained in a finite array of input registers , I = ( i1 , ... , in ) . Any integer in the input can be ... integers , and let be a function from D to the integers . We say that II computes if , 11,1 * for any ID , ( 1 , 0 ) ...
... integers , contained in a finite array of input registers , I = ( i1 , ... , in ) . Any integer in the input can be ... integers , and let be a function from D to the integers . We say that II computes if , 11,1 * for any ID , ( 1 , 0 ) ...
Page 202
... INTEGER PROGRAMMING . The knapsack problem looks at the following situation . We must select some among a set of n items . Item i has value vi , and weight w , both positive integers . There is a limit W to the total weight of the items ...
... INTEGER PROGRAMMING . The knapsack problem looks at the following situation . We must select some among a set of n items . Item i has value vi , and weight w , both positive integers . There is a limit W to the total weight of the items ...
Page 372
... integers to finite sequences of integers ( this allows 0-1 values , corresponding to decision problems ) ; let P = ( Pm , n : m , n ≥ 0 ) , be a uniform family of PRAM programs ; and let ƒ and g be functions from positive integers to ...
... integers to finite sequences of integers ( this allows 0-1 values , corresponding to decision problems ) ; let P = ( Pm , n : m , n ≥ 0 ) , be a uniform family of PRAM programs ; and let ƒ and g be functions from positive integers to ...
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