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 38
Page 427
... polynomial hierarchy : As it is built by patiently adding layer after layer , always using the previous layer as an oracle for defining the next , the resulting struc- ture is extremely fragile and ... Polynomial Hierarchy 427 The hierarchy.
... polynomial hierarchy : As it is built by patiently adding layer after layer , always using the previous layer as an oracle for defining the next , the resulting struc- ture is extremely fragile and ... Polynomial Hierarchy 427 The hierarchy.
Page 429
... polynomial hierarchy collapses to some finite level . Proof : Suppose that L is PH - complete . Since Le PH , there is an i≥ 0 such that Le Σ ; P . But any language L ' Ei + 1P reduces to L. Since all levels of the polynomial hierarchy ...
... polynomial hierarchy collapses to some finite level . Proof : Suppose that L is PH - complete . Since Le PH , there is an i≥ 0 such that Le Σ ; P . But any language L ' Ei + 1P reduces to L. Since all levels of the polynomial hierarchy ...
Page 436
... pp . 21-29 , 1986 ; also , J.CSS , 38 , pp . 68-85 , 1988 . 17.3.15 A weaker form of Theorem 17.12 was announced in 。 M. Sipser " A complexity theoretic approach to randomness 436 Chapter 17 : THE POLYNOMIAL HIERARCHY.
... pp . 21-29 , 1986 ; also , J.CSS , 38 , pp . 68-85 , 1988 . 17.3.15 A weaker form of Theorem 17.12 was announced in 。 M. Sipser " A complexity theoretic approach to randomness 436 Chapter 17 : THE POLYNOMIAL HIERARCHY.
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