Preface To the student To the educator The current edition Feedback to the author Acknowledgments
0 Introduction 0. l Automata, Computability, and Complexity Complexity theory Computability theory Automata theory 0.2 Mathematical Notions and Terminology Sets Sequences and tuples Functions and relations Graphs Strings and languages Boolean logic Summary of mathematical terms O.3 Definitions, Theorems, and Proofs Finding proofs 0.4 Types of Proof Proof by construction Proof by contradiction Proof by induction Exercises and Problems
Part One: Automata and l Regular l . l Finite Automata Formal definition of a finite automaton Examples of finite automata Formal definition of computation Designing finite automata The regular operations l .2 Nondeterminism Formal definition of a nondeterministic finite automaton Equivalence of NFAs and DFAs Closure under the regular operations l . 3 Regular Expressions Formal definition of a regular expression Equivalence with finite automata l .4 Nonregular Languages The pumping lemma for regular languages Exercises and Problems
2 Context-Free Languages 2 . l Context-free Grammars Formal definition of a context-free grammar Examples of context-free grammars Designing context-free grammars Ambiguity Chomsky normal form 2 .2 Pushdown Automata Formal definition of a pushdown automaton Examples of pushdown automata Equivalence with context-free grammars 2 . 3 Non-context-free Languages The pumping lemma for context-free languages Exercises and Problems
Part Two: Computability Theory 3 The Church-Turing Thesis 3 . l Turing Machines Formal definition of a Turing machine Examples of Turing machines 3 .2 Variants of Turing Machines Multitape Turing machines Nondeterministic Turing machines Enumerators Equivalence with other models 3 .3 The Definition of Algorithm Hilbert's problems Terminology for describing Turing machines Exercises and Problems
4 Decidability 4. l Decidable Languages Decidable problems concerning regular languages Decidable problems concerning context-free languages 4.2 The Halting Problem The diagonalization method The halting problem is undecidable A Turing-unrecognizable language Exercises and Problems
5 Reducibility 5 . l Undecidable Problems from Language Theory Reductions via computation histories 5.2 A Simple Undecidable Problem 5 . 3 Mapping Reducibility Computable functions Formal definition of mapping reducibility Exercises and Problems
6 Advanced Topics in Computability Theory 6. 1 The Recursion Theorem Self-reference Terminology for the recursion theorem Applications 6.2 Decidability of logical theories A decidable theory An undecidable theory 6. 3 Turing Reducibility 6.4 A Definition of Information Minimal length descriptions Optimality of the definition Incompressible Strings and randomness Exercises and Problems
Part Three: Complexity Theory 7 Time Complexity 7. l Measuring Complexity Big-O and small-o notation Analyzing algorithms Complexity relationships among models 7.2 The Class P Polynomial time Examples of problems in P 7.3 The Class NP Examples of problems in NP The P versus NP question 7 .4 NP-completeness Polynomial time reducibility Definition of NP-completeness The Cook-Levin Theorem 7. 5 Additional NP-complete Problems The vertex cover problem The Hamiltonian path problem The subset sum problem Exercises and Problems
8 Space Complexity 8. l Savitch's Theorem 8.2 The Class PSPACE 8 . 3 PSPACE-completeness The TQBF problem Winning strategies for games Generalized geography 8.4 The Classes Land NL 8. 5 NL-completeness Searching in graphs 8.6 NL equals coNL Exercises and Problems
9 Intractability 9. l Hierarchy Theorems Exponential space completeness 9.2 Relativization Limits of the diagonalization method 9. 3 Circuit Complexity Exercises and Problems
10 Advanced topics in complexity theory l0. l Approximation Algorithms l0.2 Probabilistic Algorithms The class BPP Primality Read-once branching programs 10.3 Alternation Alternating time and space The Polynomial time hierarchy 10.4 Interactive Proof Systems Graph nonisomorphism Definition of the model IP = PSPACE l0.5 Parallel Compuation Uniform Boolean circuits The class NC P-completeness IO.6 Cryptography Secret keys Public-key cryptosystems One-way functions Trapdoor functions Exercises and Problems
鄂公網(wǎng)安備 42010302001612號(hào) 