Computational ComplexityAddison-Wesley, 1994 - 523 Seiten This 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. |
Inhalt
ALGORITHMS | 1 |
Turing machines | 19 |
Computability | 57 |
Urheberrecht | |
19 weitere Abschnitte werden nicht angezeigt.
Häufige Begriffe und Wortgruppen
3SAT accepting Alice 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 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 polynomial-time 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